Tietojenkäsittelyteoria, kevät 2000
Harjoitus 5, to 24.2. klo 10-12 sali MaD381

1. Osoita, että kieli

   

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

2. 1. Osoita, että kieli

      

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

   2. Osoita edellisen nojalla, että kieli

      

      kuuluu luokkaan . (Lisätieto: On avoin ongelma, onko kieli MINIM -täydellinen.)

3. Osoita, että kieli

   

   on PSPACE-täydellinen. (Vihje: Todistus perustuu tietenkin Savitchin lauseeseen.)

4. Osoita, että polynomisen hierarkian kaikki luokat , , , sisältävät täydellisiä ongelmia.
5. Määritä jokin yläraja luentojen Lauseessa 3.9 (ii) konstruoidun oraakkelikielen B, jolla , tunnistamisen aikavaativuudelle.