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

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

  1. Osoita, että kieli

    displaymath711

    on NLOG-täydellinen deterministisillä Turingin koneilla logaritmisessa työtilassa laskettavien tex2html_wrap_inline713 -palautusten suhteen. (Miksi tulos ei ole mielenkiintoinen tex2html_wrap_inline715 -palautuksia käyttäen?) Ratkaisuohje: Sovella harjoitusten 3 tehtävän 6 konstruktiota.

  2. Tarkastellaan polynomisesti aikarajoitettuja oraakkelikoneita. Sanotaan, että kieli A voidaan polynomisesti Turing-palauttaa kieleen B, merkitään tex2html_wrap_inline721 , jos tex2html_wrap_inline723 , so.\ tex2html_wrap_inline725 jollakin polynomisessa ajassa toimivalla deterministisellä oraakkelikoneella M. Osoita, että luokat P ja PSPACE ovat suljettuja tex2html_wrap_inline729 -palautusten suhteen, mutta luokka NP on näiden suhteen suljettu jos ja vain jos tex2html_wrap_inline731 .
  3. Kieli A on itsepalautuva (engl. ``self-reducible''), jos on olemassa polynomisessa ajassa toimiva oraakkelikone M, jolla
    (i)
    tex2html_wrap_inline737 ;
    (ii)
    kullakin syötteellä x kone M tekee oraakkelikyselyjä vain merkkijonoista y, joilla |y| < |x|.

    Osoita, että
    1. kielet SAT ja QBF ovat itsepalautuvia (vihje: vakiosijoitukset muuttujille);
    2. jokainen itsepalautuva kieli kuuluu luokkaan PSPACE.
  4. Osoita, että kauppamatkustajan ongelma (TSP) on NP-täydellinen muodostamalla palautus tex2html_wrap_inline747 . (HC = Hamiltonin kehä -ongelma.)
  5. Osoita, että seuraava ongelma on NP-täydellinen:

    Edustajien valinta (engl. Hitting Set): Annettu kokoelma äärellisen perusjoukon S osajoukkoja tex2html_wrap_inline751 ja luonnollinen luku tex2html_wrap_inline753 . Voidaanko joukoista tex2html_wrap_inline755 valita sellaiset enintään k alkiota, että valittujen alkioiden joukossa on ainakin yksi edustaja kustakin joukosta tex2html_wrap_inline755 , tex2html_wrap_inline761 ? (Toisin sanoen: onko olemassa sellaista joukkoa tex2html_wrap_inline763 , tex2html_wrap_inline765 , että tex2html_wrap_inline767 kullakin tex2html_wrap_inline755 , tex2html_wrap_inline761 ?)
    (Vihje: Helppo palautus solmupeiteongelmasta (VC).)
  6. Etsi kirjallisuudesta (esim. kurssin kotisivun avulla) suuntaamattomien verkkojen väritysongelman (engl. Graph (3-)Colorability, Chromatic Number) NP-täydellisyystodistus ja esitä se omin sanoin.



Pekka Orponen
Thu Feb 10 22:51:56 EET 2000