Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 4, 26.4. klo 10-12 sali MaD380

1. Osoita, että NP-täydellinen kieli

   

   on kääntyvästi topattava, ja siis p-isomorfinen kielen SAT kanssa.

Olkoon aakkosto. Merkitään , ja sanotaan kielen tiheydeksi funktiota . Kieli A on (polynomisen) harva, jos jollakin polynomilla q(n) on kaikilla n, ja (eksponentiaalisen) tiheä, jos jollakin on äärettömän monella n. (Nämä määritelmät ovat ekvivalentit luentomuistiinpanojen s. 39 esitettyjen kanssa, mutta hieman helpommat käyttää.)

1. Todista luentojen Lemma 5.14: jos A ja B ovat p-isomorfisia kieliä, niin A on harva jos ja vain jos B on harva, ja A on tiheä jos ja vain jos B on tiheä.
2. Sanotaan, että kieli A voidaan tunnistaa melkein polynomisessa ajassa, jos A:lla on tunnistusalgoritmi, joka toimii polynomisessa ajassa muuten paitsi harvassa joukossa tapauksia. Merkitään melkein polynomisessa ajassa tunnistettavien kielten luokka APT:llä (engl. ``almost polynomial time''). Osoita, että SAT APT, jos ja vain jos P = NP. (Vihje: Sovella Mahaneyn lausetta 5.20.)

Ääretön kieli A on p-immuuni (engl. ``p-immune''), jos sillä ei ole yhtään ääretöntä polynomisessa ajassa tunnistettavaa osajoukkoa. Tiedetään, että luokka DEXT sisältää p-immuuneja kieliä (yksi sellainen konstruoidaan luentomuistiinpanojen Lemmassa 5.26), mutta toisaalta jokainen DEXT-täydellinen kieli sisältää äärettömiä P-osajoukkoja. On avoin ongelma, voivatko NP-täydelliset kielet olla p-immuuneja (olettaen että P ). Seuraavan tehtävän mukaan ainakaan millään ``tunnetulla luonnollisella'' NP-täydellisellä kielellä ei ole tätä ominaisuutta.

1. Osoita, että kääntyvästi topattavat kielet eivät voi olla p-immuuneja.

Kieli on p-tuotettava (engl. ``p-printable''), jos jokin polynomisessa ajassa toimiva Turingin kone tuottaa syötteellä listan joukon alkioista. On avoin ongelma, sisältääkö jokainen ääretön luokan P kieli äärettömän p-tuotettavan osakielen (so. voidaanko jokaisesta polynomisesti ratkeavasta ongelmasta tehokkaasti tuottaa polynomisia esimerkkitapauksia).

1. Todista seuraavat väitteet:
   1. Kaikki luokan P laskurikielet ovat p-tuotettavia.
   2. Kaikki p-tuotettavat kielet ovat harvoja ja kuuluvat luokkaan P.
2. Osoita, että jos jokainen ääretön luokan P kieli sisältää äärettömän p-tuotettavan osakielen, niin luokassa NP ei ole p-immuuneja kieliä. (Vihje: Sovella luokan NP kielten kvanttoriesitystä.)
3. Todista, luentomuistiinpanojen Lauseen 6.5 nojalla, seuraavat väitteet (vrt. seurauslauseen 6.8 todistus):
   1. Jos , niin luokka sisältää kieliä, jotka eivät ole -täydellisiä.
   2. Jos , niin luokka sisältää kieliä, jotka eivät ole -kovia eivätkä -kovia (so. joihin ei voi -palauttaa edellisten harjoitusten 6-tehtävän kieltä eikä kieltä ).