581336 Laskennan teoria (syksy 2003) Harjoitus 7 (2.5.12.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 7 (2.5.12.2003)

1. Osoita, että josA≤^p_mB jaB ≤^p_mCniinA≤^p_mC.

2. (a) Osoita, että josA∈PniinA≤^p_mB kaikillaB6∈ { ∅,Γ^∗}.

(b) Jos pätisiP = NP, niin mitkä kaikki kielet olisivatNP-täydellisiä?

3. Tarkastellaan suunnattujen verkkojen Hamiltonin kehä -ongelmaa:

Suunnattu Hamiltonin kehä (Directed Hamiltonian circuit, DHC) Annettu: suunnattu verkko G= (V, E)

Kysymys: onko verkossa Gsuunnattu polku, joka kulkee jokaisen solmun kautta ja palaa lähtösolmuunsa

Osoita, ettäHC≤^p_mDHC ja DHC ≤^p_m HC. Siis suunnattujen ja suuntaamattomien verkkojen Hamiltonin kehä -ongelmat ovat polynomisesti ekvivalentteja.

4. Kirjoita näkyviin SAT-ongelmanNP-täydellisyystodistuksessa esiintyvä kaavaC_t,j⁰⁰ (luennot sivu 206, nauhapää siirtyy vasemmalle). (Luentomuistiinpanoissa on kirjoitusvirhe, toisen Nauhapää siirtyy oikealle -kohdan pitäisi olla . . . vasemmalle.

5. Tarkastellaan kaavaa

φ=¬x2∨(x1∧(¬x3∨x4)).

(a) Muodosta kaavanφCNF-esitys, ts. CNF-kaava ψjollaψ(x1, x2, x3, x4) =φ(x1, x2, x3, x4) kaikilla xi.

(b) Luennoilla esitetyn konstruktion mukaisesti muodosta CNF-kaava, joka on toteutuva jos ja vain josφon toteutuva.