kuuluu vaativuusluokkaan .
(Ohje: Muodosta suunnattu verkko G, jonka solmuina ovat
kaavassa F esiintyvät muuttujat ja niiden negaatiot, ja
jossa on kaari literaalista
literaaliin
, jos
ja vain jos kaava F sisältää tekijänään implikaation
, so. disjunktion
.
Totea, että kaavan F ristiriitaisuus, so. toteutumattomuus,
voidaan muotoilla verkon G saavutettavuusongelmana.)
kuuluu vaativuusluokkaan = co-NP.
(Merkintä ``
'' tarkoittaa, että kaavat toteutuvat
täsmälleen samoilla muuttujien totuusarvoasetuksilla.)
kuuluu luokkaan .
(Lisätieto: On avoin ongelma, onko kieli MINIM
-täydellinen.)
on PSPACE-täydellinen. (Vihje: Todistus perustuu tietenkin Savitchin lauseeseen.)