on tautologia eli kun kaava
ei ole toteutuva.
Määritellään muunnos f asettamalla
Tällöin .
Muunnos f on polynomisessa ajassa laskettava, joten EQUIV
.
Kieliluokka co-NP on suljettu polynomisessa ajassa laskettavien muunnosten
suhteen
(harjoitus 2, tehtävä 4 b). Koska SAT NP,
co-NP
ja myös EQUIV
co-NP =
.
Helposti nähdään, että MINIM = B
polynomilla
q(n) = n - 1:
Koska EQUIV ,
co-
=
ja MINIM
.
Olkoon NP. Tällöin lauseen 3.2 kohtien
perusteella ja oletuksen mukaan
NP.
Näin nähdään, että NP = co-NP.
Olkoon NP ja
. Tällöin
P(A) eli kieli
B
tunnistetaan deterministisesti polynomisessa ajassa jollakin
oraakkelikoneella M
ja oraakkelilla A. Korvataan M:n tilassa
tapahtuva oraakkelikysely
kielet
A ja
tunnistavien epädeterminististen Turingin koneiden
N ja N'
simuloinnilla seuraavasti:
Ensin simuloidaan konetta N oraakkelinauhalla olevalla syötteellä. Jos N
hyväksyy
syötteen, jatketaan M:n tilasta . Jos N
hylkää syötteen,
syöte voi silti kuulua kieleen A. Silloin simuloidaan konetta N'
oraakkelinauhalla
olevalla syötteellä. Jos N hyväksyy syötteen, jatketaan M:n tilasta
. Jos N hylkää syötteen, jatketaan M:n tilasta
.
Modifioitu M toimii ekvivalentisti alkuperäisen M:n kanssa epädeterministisenä Turingin koneena, joka tunnistaa kielen B polynomisessa ajassa, sillä M tekee oraakkelikyselyjä polynomisen määrän, joihin N ja N' antavat vastauksen polynomisessa ajassa. Näin nähdään, että NP on suljettu pT-palautusten suhteen.
SAT( ):
Jos = 1 tai
= 1, niin hyväksy, muuten hylkää.
QBF( ):
-tapauksessa palauta tulos
,
-tapauksessa
.
Todistus. Olkoon A = L(M, A), missä M on polynomisessa ajassa p(n) toimiva oraakkelikone.
Konetta M voidaan ajatella myös ``rekursiivisena ohjelmana'' ja simuloida
sen toimintaa pinon
avulla: aina kun M syötteellä x tekee oraakkelikyselyn jonosta y, |y|
< |x|, talletetaan
M:n kyselyhetkinen tilanne pinoon ja käynnistetään uusi M:n laskenta
syötteellä y.
Tällöin syötteellä x, jonka pituus on n, pinossa voi kerrallaan olla
enintään n talletettua
tilannetta, kukin kooltaan O(p(n)) merkkiä. Siten konetta M voidaan
simuloida tilassa
O(np(n)).
löytämät merkkeihin johtavat laskennat kuuluvat epädeterministisen
koneen tilannepuun
eri polkuihin, mikä ei takaa, että olisi olemassa jokin polku, joka tuottaa
yhtä aikaa kaikki
merkit
. Siksi tällä menetelmällä ei voida todistaa, että
NTIME
ASPACE(s(n)).
Todistus. Olkoon 0. Jos vaihdetaan keskenään
-koneen hyväksyvät ja
hylkäävät tilat sekä eksistentiaaliset ja universaaliset tilat, saadaan
-kone, joka
tunnistaa alkuperäisen koneen tunnistaman kielen komplementin. Siten
väitteen
P =
todistaminen riittää, koska silloin
P = co-
P =
co-
=
.
Väite on tosi indekseillä k = 0 ja k = 1, sillä -kone on
deterministinen Turingin kone
ja
-kone on epädeterministinen Turingin kone, ja siten
=
= P
=
P =
P,
= NP =
P ja
=
co-NP =
P.
Olkoon 1. Oletetaan, että
P =
ja
P =
(induktio-oletus).
Nyt jollakin polynomilla q, missä kieli B kuuluu
luokkaan
,
joka on induktio-oletuksen mukaan sama kuin luokka
P. Olkoon M
kielen B
polynomisessa ajassa tunnistava
-kone.
Alternoiva eksistentiaalisessa tilassa aloittava Turingin kone N
generoikoon
epädeterministisesti kaikki merkkijonot y, joilla ,
ja testatkoon
merkkijonon
kuulumisen kieleen B kuten M. Jos M
hyväksyy
:n jollakin y, niin N hyväksyy, muuten hylkää
x:n.
Kone N tunnistaa kielen , sillä
Kielen A tunnistaminen koneella N tapahtuu polynomisessa ajassa, sillä
syötteellä x
merkkijonon muodostaminen ja testaaminen kieleen B
kuuluvaksi
konetta M simuloiden tapahtuvat polynomisessa ajassa.
Kone N alternoi tasan yhden kerran useammin kuin M, joka alternoi
enintään k - 1 kertaa,
joten N alternoi enintään k kertaa. Alkutilan mukaan N on -kone.
Koska kieli A tunnistetaan polynomisessa ajassa -koneella,
P.
Olkoon M polynomisessa ajassa q kielen A tunnistava -kone.
Määritellään Continue
kieleksi, johon kuuluvat koneen M hyväksymiseen
johtavat
universaaliset tilanteet
, joista lähtien M pysähtyy ajassa
ja alternoi enintään k - 1 kertaa. Saavutettavasta tilanteesta alkava
M:n laskenta
pysähtyy vaaditussa ajassa ja sallituilla alternaatioilla, joten
Continue
sisältää
kaikki saavutettavat hyväksymiseen johtavat universaaliset tilanteet.
Kieli Continue tunnistetaan alternoivalla Turingin koneella N, jonka
alkutila on
universaalinen. Tämä kone tarkistaa, että syöte on syntaktisesti
kelvollinen, kirjoittaa annetun
tilanteen
nauhasisällöt työnauhoilleen, siirtää nauhapäät
tilannetta
vastaavaan kohtaan ja simuloi sitten konetta M jatkaen laskentaa
tilanteeseen
kuuluvassa koneen tilassa. Koneen N laskenta-aikaa rajoitetaan laskurilla,
jonka
alkuarvoksi asetetaan
ja jota vähennetään yhdellä jokaisen
simulointiaskelen
jälkeen. Jos laskuri nollautuu, N hylkää syötteen.
Koneen M alternaatioita seuraava kone N alternoi enintään k - 1
kertaa. Alkutilan mukaan
N on -kone.
Kone N tunnistaa kielen Continue polynomisessa ajassa, sillä syötteen
tarkistaminen
ja siirtäminen työnauhoille sekä jatkolaskenta konetta M aikarajoitetusti
simuloiden
tapahtuvat polynomisessa ajassa. Koska N on
-kone, kieli
Continue
kuuluu
luokkaan
P, joka on induktio-oletuksen mukaan sama kuin luokka
.
Määritellään kielet
Nyt pätee
eli jollakin polynomilla q.
Kieli B tunnistetaan epädeterministisesti polynomisessa ajassa, joten . Koska
Continue
, myös
. Kieli D tunnistetaan epädeterministisesti polynomisessa
ajassa koneella,
joka tarkistaa syötteen olevan muotoa
, simuloi
konetta M syötteellä
x ensimmäiseen alternaatioon saakka ja tällöin vertaa
:aa
saavutettuun tilanteeseen.
Tämä kone hylkää syötteet, joilla laskenta päättyy ennen M:n ensimmäistä
alternaatiota.
Tiedetään, että ja
. Siten
ja, koska
on
suljettu polynomirajoitetun eksistenssikvantifioinnin suhteen, myös
ja edelleen
.
Todistus. Selvästi P =
.
Olkoon A = L(M), missä M on -kone, time
,
q polynomi.
Tällöin kuvaus
on polynomisessa ajassa laskettava palautus kielestä A kieleen .