MAT340 Tietojenkäsittelyteoria
1. välikoe ke 1.3.2000 klo 8-11

1. Todista, että kieli

   

   on -täydellinen -palautusten suhteen.

2. Osoita, että seuraava ongelma on NP-täydellinen:

   Hallitseva joukko (engl. Dominating Set): Annettu suuntaamaton verkko G = (V,E) ja kokonaisluku k. Voidaanko verkosta G valita enintään k solmun joukko niin, että valitusta joukosta johtaa kaari jokaiseen joukon ulkopuolelle jäävään solmuun (so. jos , niin jollakin on )?

   (Vihje: Vrt. solmupeiteongelma.)
3. 1. Osoita, että jos , niin . (Vihje: Tarkastele syötteitä, jotka ovat muotoa , q polynomi.)
   2. Päättele (a)-kohdan tuloksesta, että välttämättä on .
   Lisätieto: Samaa ``toppaustekniikkaa'' käyttäen voidaan osoittaa myös, että jos , niin .
4. Hahmottele todistus sen osoittamiseksi, että kaikilla seuraava kieli on -täydellinen:

   

   (Vihjeitä: Cook, Wrathall, alternoivat ja/tai oraakkelikoneet.)

Pisteytys: tehtävät 1 ja 4 á 7 pistettä, tehtävät 2 ja 3 á 8 pistettä, yhteensä 30 pistettä.