TIE311 Algoritmiteorian jatkokurssi (2 ov)
Kurssikoe, kevät 1999
Kuulustelija: Pekka Orponen

Tehtävien ratkaisemisen apuna saa käyttää mitä tahansa lähdemateriaalia; ratkaisut tulee kuitenkin laatia henkilökohtaisesti. Vastaukset palautetaan kuulustelijalle henkilökohtaisesti tai suljetussa kirjekuoressa huoneen MaD307 viereiseen postilaatikkoon perjantaihin 21.5. klo 16 mennessä. Kukin tehtävä 15 pistettä, yhteensä 60 pistettä.

1. Sanotaan, että kieli A kuuluu luokkaan APC (engl. ``almost polynomially correct''), jos A:lla on polynomisessa ajassa toimiva tunnistusalgoritmi, joka kuitenkin voi polynomisen harvassa joukossa tapauksia antaa väärän vastauksen. Osoita, että SAT APC jos ja vain jos P = NP. (Vihjeitä: Toppaus, äänestys.)
2. Palautetaan mieliin seuraava määritelmä (harjoituksesta 4): Ääretön kieli A on p-immuuni (engl. ``p-immune''), jos sillä ei ole yhtään ääretöntä polynomisessa ajassa tunnistettavaa osajoukkoa. Osoita, että kaikilla kieli

   

   on P-immuuni. (Toisin sanoen: jokainen ääretön P-joukko sisältää jonkin merkkijonon x, jolla , .) [Merkinnät määritelty luentojen ss. 104-105.]

3. Tarkastellaan Kolmogorov-satunnaisten merkkijonojen joukkoa

   

   [luennot, s. 102]. Osoita, että kaikilla on voimassa , jollakin x:stä riippumattomalla vakiolla c. (Vihje: Osoita, että kaikilla on voimassa , sopivalla vakiolla c. Tätä varten totea ensin, että jos R-yhteensopiva ic-ohjelma p hyväksyy merkkijonon x, niin , jollakin x:stä ja p:stä riippumattomalla vakiolla d.)

4. Tehtäväpaperin kääntöpuolella on kopio todistuksesta, jossa luokan NP todistussysteemikarakterisointia NP = PCP(O(log n), O(1)) [luennot, s. 121] hyväksi käyttäen osoitetaan, että klikkiongelmalla ei voi olla polynomisessa ajassa toimivaa 1/2-approksimointialgoritmia, paitsi jos P = NP.

   Osoita samaa tekniikkaa käyttäen vastaava approksimoitumattomuustulos seuraavalle NP-täydelliselle pisin yhteinen alijono -ongelmalle (engl. ``longest common subsequence'', LCS). Merkkijono on merkkijonon alijono, jos jollakin indeksijonolla on . (Huom.: alijonon s merkit sijaitsevat siis jonossa t järjestyksessä, mutta eivät välttämättä peräkkäin.) LCS-ongelmassa syötteenä annetaan kokoelma merkkijonoja , ja tehtävänä on määrittää pisin merkkijono, joka esiintyy niissä kaikissa alijonona.