next up previous
Next: About this document Up: No Title Previous: No Title

Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 3: ratkaisuja (KP, PO täyd. & tark.)

    1. Merkkijono x kuuluu kieleen EQUIV täsmälleen silloin, kun kaava

      displaymath375

      on tautologia eli kun kaava

      displaymath377

      ei ole toteutuva.

      Määritellään muunnos f asettamalla

      displaymath379

      Tällöin tex2html_wrap_inline782 . Muunnos f on polynomisessa ajassa laskettava, joten EQUIV tex2html_wrap_inline786 .

      Kieliluokka co-NP on suljettu polynomisessa ajassa laskettavien muunnosten suhteen (harjoitus 2, tehtävä 4 b). Koska SAT tex2html_wrap_inline788 NP, tex2html_wrap_inline790 co-NP ja myös EQUIV tex2html_wrap_inline788 co-NP = tex2html_wrap_inline794 .

    2. Kieleen B kuulukoot syntaktisesti kelvolliset lausekalkyylin kaavat. Tämä kieli tunnistetaan polynomisessa ajassa, siis B tex2html_wrap_inline788 P.

      Helposti nähdään, että MINIM = B tex2html_wrap_inline798 tex2html_wrap_inline800 polynomilla q(n) = n - 1:

      displaymath391

      Koska EQUIV tex2html_wrap_inline810 , tex2html_wrap_inline812 co- tex2html_wrap_inline794 = tex2html_wrap_inline816 ja MINIM tex2html_wrap_inline818 .

    1. Olkoon tex2html_wrap_inline896 (mahdollisesti kvantifioitu) lausekalkyylin kaava ja x jokin tässä kaavassa esiintyvä muuttuja. Merkitään tex2html_wrap_inline900 :llä kaavaa, joka saadaan tex2html_wrap_inline896 :stä sijoittamalla x:lle arvo tex2html_wrap_inline906 ja sieventämällä. Voidaan todeta, että aina on tex2html_wrap_inline908 . Tämän perusteella saadaan kielille SAT ja QBF seuraavat itsepalautusalgoritmit:

      SAT( tex2html_wrap_inline896 ):

      • Jos tex2html_wrap_inline896 :ssä ei ole yhtään muuttujaa, määritä sen vakioarvo; jos tex2html_wrap_inline914 , niin hyväksy, muuten hylkää.
      • Muuten olkoon x jokin tex2html_wrap_inline896 :n muuttuja. Määritä oraakkelikutsuilla totuusarvot tex2html_wrap_inline920 ja tex2html_wrap_inline922 :

        displaymath426

        displaymath429

        Jos tex2html_wrap_inline920 = 1 tai tex2html_wrap_inline922 = 1, niin hyväksy, muuten hylkää.

      QBF( tex2html_wrap_inline896 ):

      • Jos kaava tex2html_wrap_inline896 on kvanttoriton, määritä sen arvo suoraan.
      • Muuten on kaksi tapausta: tex2html_wrap_inline932 ja tex2html_wrap_inline934 jollakin kaavalla tex2html_wrap_inline936 . Määritä oraakkelikutsuilla totuusarvot tex2html_wrap_inline920 ja tex2html_wrap_inline922 :

        displaymath434

        displaymath437

        tex2html_wrap_inline942 -tapauksessa palauta tulos tex2html_wrap_inline944 , tex2html_wrap_inline946 -tapauksessa tex2html_wrap_inline948 .

    2. Väite. Jos kieli A on itsepalautuva, niin tex2html_wrap_inline820 PSPACE.

      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)). tex2html_wrap_inline988

  1. Jos simuloitava kone on epädeterministinen, on mahdollista, että tarkistuksen

    displaymath444

    löytämät merkkeihin tex2html_wrap_inline990 johtavat laskennat kuuluvat epädeterministisen koneen tilannepuun eri polkuihin, mikä ei takaa, että olisi olemassa jokin polku, joka tuottaa yhtä aikaa kaikki merkit tex2html_wrap_inline990 . Siksi tällä menetelmällä ei voida todistaa, että NTIME tex2html_wrap_inline994 ASPACE(s(n)).

  2. Väite. Kaikilla tex2html_wrap_inline998 0 on tex2html_wrap_inline1000 P = tex2html_wrap_inline1002 ja tex2html_wrap_inline1004 P = tex2html_wrap_inline1006 .

    Todistus. Olkoon tex2html_wrap_inline998 0. Jos vaihdetaan keskenään tex2html_wrap_inline1004 -koneen hyväksyvät ja hylkäävät tilat sekä eksistentiaaliset ja universaaliset tilat, saadaan tex2html_wrap_inline1000 -kone, joka tunnistaa alkuperäisen koneen tunnistaman kielen komplementin. Siten väitteen tex2html_wrap_inline1000 P = tex2html_wrap_inline1002 todistaminen riittää, koska silloin tex2html_wrap_inline1004 P = co- tex2html_wrap_inline1000 P = co- tex2html_wrap_inline1002 = tex2html_wrap_inline1006 .

    Väite on tosi indekseillä k = 0 ja k = 1, sillä tex2html_wrap_inline1030 -kone on deterministinen Turingin kone ja tex2html_wrap_inline1032 -kone on epädeterministinen Turingin kone, ja siten tex2html_wrap_inline1034 = tex2html_wrap_inline1036 = P = tex2html_wrap_inline1030 P = tex2html_wrap_inline1040 P, tex2html_wrap_inline816 = NP = tex2html_wrap_inline1032 P ja tex2html_wrap_inline794 = co-NP = tex2html_wrap_inline1048 P.

    Olkoon tex2html_wrap_inline998 1. Oletetaan, että tex2html_wrap_inline1000 P = tex2html_wrap_inline1002 ja tex2html_wrap_inline1004 P = tex2html_wrap_inline1006 (induktio-oletus).

    On osoitettu, että jos tex2html_wrap_inline998 1 ja tex2html_wrap_inline1000 P = tex2html_wrap_inline1002 ja tex2html_wrap_inline1004 P = tex2html_wrap_inline1006 , niin tex2html_wrap_inline1130 P = tex2html_wrap_inline1256 . Komplementtiluokkia koskevan huomion mukaan tällöin on voimassa myös väite tex2html_wrap_inline1276 P = tex2html_wrap_inline1278 . Koska väite on todistettu, kun k = 0 ja k = 1, sen voimassaolo kaikilla tex2html_wrap_inline998 0 seuraa induktiosta. tex2html_wrap_inline988
  3. Väite. Kun tex2html_wrap_inline1288 , tex2html_wrap_inline1290 on tex2html_wrap_inline1002 -täydellinen.

    Todistus. Selvästi tex2html_wrap_inline1294 P = tex2html_wrap_inline1002 .

    Olkoon A = L(M), missä M on tex2html_wrap_inline1000 -kone, time tex2html_wrap_inline1304 , q polynomi. Tällöin kuvaus

    displaymath495

    on polynomisessa ajassa laskettava palautus kielestä A kieleen tex2html_wrap_inline1290 . tex2html_wrap_inline988


next up previous
Next: About this document Up: No Title Previous: No Title

Pekka Orponen
Wed Apr 21 18:24:48 EET DST 1999