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

Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 3, 19.4. klo 10-12 sali MaD380

    1. Osoita, että kieli

      displaymath686

      kuuluu luokkaan tex2html_wrap_inline702 = co-NP. (Merkintä `` tex2html_wrap_inline704 '' tarkoittaa, että kaavat toteutuvat täsmälleen samoilla muuttujien totuusarvoasetuksilla.)

    2. Osoita edellisen nojalla, että kieli

      displaymath687

      kuuluu luokkaan tex2html_wrap_inline714 . (Lisätieto: Kieli MINIM on itse asiassa tex2html_wrap_inline714 -täydellinen.)

  1. Osoita, että luokka NP on suljettu pT-palautusten suhteen, jos ja vain jos NP = co-NP.
  2. Kieli A on itsepalautuva (engl. ``self-reducible''), jos on olemassa polynomisessa ajassa toimiva oraakkelikone M, jolla
    (i)
    A = L(M,A);
    (ii)
    kullakin syötteellä x kone M tekee oraakkelikyselyjä vain merkkijonoista y, joilla |y| < |x|.

    Osoita, että
    1. kielet SAT ja QBF ovat itsepalautuvia;
    2. jokainen itsepalautuva kieli kuuluu luokkaan PSPACE.
  3. Miksi luentojen lauseen 4.10 (`` tex2html_wrap_inline732 '') todistus edellyttää, että simuloitava kone on deterministinen (eikä esim. epädeterministinen)?

    KÄÄNNÄ

  4. Alternoiva Turingin kone on tex2html_wrap_inline734 -kone ( tex2html_wrap_inline736 -kone), tex2html_wrap_inline738 , jos sen alkutila on eksistentiaalinen (universaalinen), ja missä tahansa koneen laskennassa (so. millä tahansa laskentapolulla) koneen tila vaihtuu eksistentiaalisesta universaaliseksi tai toisinpäin (kone ``alternoi'') enintään k-1 kertaa. Lisäksi voidaan deterministisiä koneita sanoa tex2html_wrap_inline742 - tai tex2html_wrap_inline744 -koneiksi. Määritellään vaativuusluokat:

    eqnarray391

    Osoita, että kaikilla tex2html_wrap_inline762 on tex2html_wrap_inline764 ja tex2html_wrap_inline766 . (Ohje: Todistus induktiolla k:n suhteen. Induktioaskelta varten tarkastele mielivaltaisen polynomisessa ajassa toimivan tex2html_wrap_inline770 -koneen M tunnistamaa kieltä A, ja sen rinnalla kieltä

    displaymath688

    Totea, että kieli tex2html_wrap_inline780 kuuluu luokkaan tex2html_wrap_inline766 , ja että väite tex2html_wrap_inline784 seuraa tästä pienillä lisätarkasteluilla. Huom.: Vastaavalla argumentilla voidaan osoittaa, että Savitchin lauseen seurauksena on

    displaymath689

    kaikilla tex2html_wrap_inline762 .)

  5. Osoita, että kaikilla tex2html_wrap_inline738 seuraava kieli on tex2html_wrap_inline790 -täydellinen:

    displaymath690

    Lisätieto (ei tarvitse todistaa): Jonkin verran luonnollisempi tex2html_wrap_inline790 -täydellisten kielten perhe on:

    displaymath691



Pekka Orponen
Wed Apr 21 18:32:54 EET DST 1999