Bonyolultságelmélet. SZTE Informatikai Tanszékcsoport

´ ´ Bonyolultsagelm elet ´ ´ Esik Zoltan ´ SZTE Informatikai Tanszekcsoport ´ ıtástudomany ´ Alapjai Tanszek ´ Szam´

´ ıthatos ´ ag ´ elmelet ´ enek ´ ´ A kiszam´ kialakulasa ´ aja ´ 1900: Hilbert 10. problem ´ Adott f (x1 , . . . , xn ) = g(x1 , . . . xn ) diofantikus egyenlet, ahol f es ´ egyutthat ´ polinomok, letezik-e ´ ´ ert ´ ek ´ u) g egesz ¨ os (egesz ˝ ´ megoldasa.

1971: Matijaseviˇc ´ aja ´ algoritmikusan megoldhatatlan. Hilbert 10. problem

1928: Hilbert ´ ´ Talaljunk olyan algoritmust, amellyel a predikatumkalkulus ´ ˝ ´ er ´ ol ˝ eldonthetj ¨ (fuggv ¨ enykalkulus) tetszoleges kijelentes uk, ¨ ´ ´ hogy ervenyes-e.

´ ¨ 1930-as evek kozepe: Church, Turing ´ Ilyen algoritmus nem letezik.

´ ´ Bonyolultsagelm elet

2 / 184

´ ıthatos ´ ag ´ elmelet ´ enek ´ ´ A kiszam´ kialakulasa

◮ ◮ ◮

¨ ´ 1931, Godel: Primit´ıv rekurz´ıv fuggv ¨ enyek ´ anos ¨ ´ ´ 1934, Godel: Altal rekurz´ıv fuggv ¨ enyek ´ 1930-as evek eleje, Church, Kleene, Rosser (Princeton): ´ ´ ag ´ λ-definialhat os

¨ ¨ 1935: AMS New York-i osszej ovetele ´ ´ anos ´ ´ Church tezise: Az altal rekurz´ıv fuggv ¨ enyek (matematikai ´ ıthato´ fuggv ´ fogalom) megfelelnek az algoritmikusan kiszam´ ¨ eny ´ fogalmanak (intuit´ıv fogalom).

1936: Kleene ´ anos ´ ´ Az altal rekurz´ıv fuggv ¨ enyek megegyeznek a ´ ´ λ-definialhat o´ fuggv ¨ enyekkel. ´ ´ Bonyolultsagelm elet

3 / 184

´ ıthatos ´ ag ´ elmelet ´ enek ´ ´ A kiszam´ kialakulasa 1936: Turing ´ ekvivalens a Bebizony´ıtja, hogy a Turing-gep ´ ´ aggal, ´ ´ megfogalmazza azt a tezist, ´ λ-definialhat os es hogy a ´ megfelel az algoritmussal kiszam´ ´ ıthato´ Turing-gep ´ fuggv ¨ enyeknek. ´ ´ ´ matematikai A Church-Turing tezist tapasztalati tenyek es ´ ´ ´ ´ eredmenyek tamasztjak ala: ◮ Minden intuit´ıv ertelemben ´ ´ ar ´ ol ´ megoldhato´ problem ´ a matematikai sikerult ¨ kimutatni, hogy azok megoldhatok modellekben is. ◮

A matematikai modellek ekvivalensek.


4 / 184

´ ıthatos ´ ag ´ es ´ bonyolultsag ´ Kiszam´ ´ ıthatos ´ agelm ´ ´ Kiszam´ elet ´ ak? ´ Melyek az algoritmikusan megoldhato´ problem

´ ´ Bonyolultsagelm elet ´ ak, ´ eroforr ˝ ´ eny. ´ Melyek a gyakorlatilag megoldhato´ problem asig

1971: Cook ´ NP osztalyok, ´ ´ SAT NP-teljes P es NP-teljesseg,

1972: Karp ´ ´ ak ´ valtozatoss ´ ´ ara. ´ Ramutat az NP-teljes problem ag

1973: Levin ¨ kombinatorikus problema ´ ´ a kimer´ıto˝ Tobb ,,univerzalis ´ keresesre”.


5 / 184

´ ´ osztalyok ´ ´ szam´ ´ ıtasi ´ modok ´ Tovabbi bonyolultsagi es

◮

L, NL, PSPACE, EXP, . . . ´ ınus ´ modellek Valosz´ ˝ egi

◮

´ ´ ıtas ´ Parhuzamos szam´

◮

stb.


6 / 184

˝ ´ ak ´ Polinom idoben megoldhato´ problem ˝ EG ´ ´ ELERHET OS ◮

◮ ◮

´ ıtott graf. ´ Adott: egy G = (V, E) irany´ Feltehetjuk, ¨ hogy V = {1, 2, . . . , n}. ´ es: ´ letezik-e ´ ˝ n-be vezeto˝ irany´ ´ ıtott ut? Kerd 1-bol ´ ´ Modszer: 1. S := {1}. ¨ uk 2. Jelolj ¨ meg az 1 csucsot. ´ 3. Am´ıg S nem ures: ¨ ´ 3.1 Valasztunk egy i ∈ S csucsot. ´ 3.2 S := S − {i}. 3.3 j = 1..n: ´ j nem megjelolt, ¨ Ha (i, j) ∈ E es ´ jelolj ¨ uk akkor S := S ∪ {j} es ¨ meg j-t.

◮

¨ csucs, ´ Ha n megjelolt ´ adjunk igen valaszt, ¨ ´ kul ¨ onben adjunk nem valaszt.


7 / 184

˝ ´ ak ´ Polinom idoben megoldhato´ problem ´ any ´ kimaradt reszlet ´ Neh ◮

◮

´ – pl. szomszeds ´ agi ´ matrix ´ A bemenet megadasa ˝ de lenyeges ´ ´ (Fugg ¨ a modelltol, szerepet nem jatszik.) ´ asa ´ S reprezental ◮ ◮

´ ´ kereses ´ sor: szeless egi ´ egi ´ kereses ´ verem: egyfajta melys

´ ´ Hatekonys ag ◮ ◮

´ ´ legfeljebb egyszer hasznaljuk ´ A matrix minden elemet fel. ´ ´ ´ Ha az egyszeru˝ muveletek ˝ (S egy elemenek kivalaszt asa, ¨ ese, ´ ˝ eny ´ uek, megjelol stb.) konstans idoig ˝ akkor O(n2 ).

˝ EG ´ ´ egy eldont ¨ esi ´ problema. ´ Az ELERHET OS ´ ´ Bonyolultsagelm elet

8 / 184

˝ ´ ak ´ Polinom idoben megoldhato´ problem ´ MAXIMALIS FOLYAM ◮

´ ozat, ´ ahol Adott: egy (V, E, s, t, c) hal ◮ ◮ ◮

◮

´ ıtott graf, ´ (V, E) egy irany´ ´ t ∈ V nyelo, ˝ t elerhet ´ ˝ s ∈ V forras, o˝ s-bol ´ (u, v) ∈ E ⇒ c(u, v) ∈ N+ kapacitas

´ ek ´ u˝ folyam? ´ es: ´ mekkora a legnagyobb ert Kerd

´ ´ amire: Folyam: f : E → N0 lekepez es, ◮ ◮

(u, v) ∈ E ⇒ 0 ≤ f (u, v) ≤ c(u, v); P P f (v, u). f (u, v) = v∈ / {s, t} ⇒ (v,u)∈E

(u,v)∈E

´ eke: ´ A folyam ert X

f (s, u).

(s,u)∈E ´ ´ Bonyolultsagelm elet

9 / 184

´ al ´ ozat ´ Segedh

´ ıtas ´ All´ ´ csak akkor letezik ´ ´ nagyobb ert ´ ek ´ u˝ f ′ Akkor es az f folyamnal ´ ´ ozatban ´ ´ ˝ folyam, ha az alabbi N(f ) hal t elerhet o˝ s-bol: N(f )

=

(V, E′ , s, t, c′ )

E′

=

(E − {(u, v) : f (u, v) = c(u, v)}) ∪

c′ (u, v)

=

{(v, u) : (u, v) ∈ E, f (u, v) > 0} c(u, v) − f (u, v) ha (u, v) ∈ E ∩ E′ ; ¨ f (v, u) kul ¨ onben.

´ ´ arokat.) ´ (N(f ) tartalmazhat ellentetes elp


10 / 184

Jav´ıto´ ut ´

´ Az f folyam jav´ıtasa ˝ t-be vezeto˝ ut. Tegyuk ¨ fel, hogy N(f )-ben adott egy s-bol ´ ˝ ´ elkapacit ´ ´ Legyen d az uton ´ elofordul o´ minimalis as. ´ Minden (u, v) elre legyen  ˝ az uton ´  f (u, v) + d ha (u, v) ∈ E ∩ E′ elofordul ′ ˝ f (u, v) = f (u, v) − d ha (v, u) ∈ / E elofordul az uton ´  ¨ f (u, v) kul ¨ onben. ´ d-vel nagyobb ert ´ ek ´ u˝ folyam. Ekkor az f ′ az f -nel


11 / 184

´ Modszer 1. Kezdetben f legyen az azonosan nulla folyam. ´ ıtsuk ´ ozatot. ´ 2. Kesz´ ¨ el az N(f ) hal ´ ˝ akkor f maximalis. ´ 3. Ha N(f )-ben t nem erhet o˝ el s-bol, ¨ ˝ t-be vezeto˝ uthoz ´ annak minimalis ´ 4. Kul ¨ onben egy s-bol ´ es ′ ´ u´ el ´ ehez ´ ´ ıtsuk kapacitas kesz´ ¨ el az f folyamot, legyen ´ menjunk ¨ vissza a 2. pontra. f := f ′ es

´ ´ Hatekonys ag ◮ ◮

◮

C := max{c(u, v) : (u, v) ∈ E}. ´ es, ´ lep ´ esenk ´ ´ O(n2 ) ido: ˝ O(n3 C). O(nC) lep ent ´ Ez NEM POLINOMIALIS. (C miatt.) ´ szeless ´ ´ valtozat ´ ´ Az utkeres ´ es egi aval: O(n5 ).

´ ´ asi ´ problema. ´ A MAXIMALIS FOLYAM optimalizal ´ ¨ esi ´ valtozata: ´ Eldont MAXIMALIS FOLYAM(E). ´ ´ Bonyolultsagelm elet

12 / 184

¨ problema ´ Az utazo´ ugyn ¨ ok TSP ◮

◮

◮

´ ´ barmely ´ ´ i, j varos ´ Adott: az 1, 2, . . . , n varosok es ket ´ ´ tavols aga: di,j . ´ es: ´ talaljunk ´ ¨ ´ Kerd egy, az osszes varost pontosan egyszer ´ ¨ ¨ erint o˝ legrovidebb korutat. ¨ esi ´ valtozata: ´ TSP(E). Eldont (n−1)! ´ modszer: ´ ¨ ´ ¨ ut Trivialis az osszes lehetseges kor ´ 2 ´ ´ ´ megvizsgalasaval.

´ polinom ideju˝ Nem ismert, hogy TSP megoldhato-e algoritmussal. ´ (NP-teljes problema.)


13 / 184

Defin´ıcio´ ´ Legyenek f , g : N → N fuggv ¨ enyek. ◮ f (n) = O(g(n)), ha letezik ´ olyan c > 0, hogy f (n) ≤ c · g(n) majdnem minden n-re. ◮

f (n) = Ω(g(n)), ha g(n) = O(f (n)).

◮

´ g(n) = O(f (n)). f (n) = Θ(g(n)), ha f (n) = O(g(n)) es

´ Pelda p(n) = a0 nk + a1 nk−1 + . . . + ak q(n) = b0 nℓ + b1 nℓ−1 + . . . + bℓ ahol ai , bj ∈ N, a0 , b0 > 0. Ekkor: ◮

p(n) = O(q(n)) ⇔ k ≤ ℓ;

◮

p(n) = Θ(q(n)) ⇔ k = ℓ.

Legyen a ∈ N, a > 1. Ekkor p(n) = O(an ), de an 6= O(p(n)).


14 / 184

´ A P osztaly

Defin´ıcio´ ´ ´ esik, ha megoldhato´ polinom Egy problema a P osztalyba ˝ eny ´ u˝ (vagy O(nk ) idoig ˝ eny ´ u) idoig ˝ algoritmussal.

´ tezis ´ A polinomialis ◮

◮

´ ıto˝ megoldast ´ Egy algoritmus akkor ad gyakorlatilag kieleg´ ´ ara, ´ ˝ eny ´ u. egy problem ha polinom idoig ˝ ´ at ´ akkor tekintunk Egy problem ¨ gyakorlatilag ´ ´ ha a P osztalyba esik. megoldhatonak,


15 / 184

´ any ´ ellenvetes ´ Neh ◮

◮

´ a gyakorlatban egy O(n100 ) idoig ˝ eny ´ u˝ Elfogadhato-e algoritmus? ´ A konstansok nagysaga.

◮

´ u˝ adatokon egy exponencialis ´ algoritmus is Kismeret ´ (de csak veges ´ jobban viselkedhet, mint egy polinomialis sok adaton). ´ ´ Legrosszabb eset – varhat o´ viselkedes.

◮

´ ´ ´ Hatekony parhuzamos´ ıtas.

◮

Ugyanakkor ◮ ◮

◮

˝ ´ ak ´ rendje kicsi. A gyakorlatban elofordul o´ P-beli problem ´ robusztus, es ´ elegans ´ matematikai elmelethez ´ A P osztaly vezet. ´ okat ´ ´ ´ Fontos informaci szolgaltat a hatekonyan megoldhato´ ´ ak ´ szerkezeter ´ ol. ˝ problem


16 / 184

´ ´ Turing-gepek defin´ıcioja

Defin´ıcio´ ´ egy (K, Σ, δ, s) negyes, ´ Turing-gep: ahol ◮ K az allapotok ´ ´ veges, nemures ¨ halmaza; ◮

´ ´ Σ a betuk ˝ (szimbolumok) veges, nemures ¨ halmaza;

◮

δ : K × Σ → (K ∪ {,,igen”, ,,nem”, h}) × Σ × {←, −, →} az ´ ´ atmenetf uggv ¨ eny;

◮

´ s ∈ K a kezdo˝ allapot.

⊲, ⊔ ∈ Σ, Σ − {⊲, ⊔} = 6 ∅, ´ δ(q, ⊲) = (p, σ, d) ⇒ σ = ⊲, d =→ (legalabbis d 6=←).


17 / 184

´ ´ Pelda: jobbra tolas


p∈K s s s s q q q q q0 q0 q0 q0 q1 q1 q1 q1

σ∈Σ ⊲ 0 1 ⊔ ⊲ ⊔ 0 1 ⊲ ⊔ 0 1 ⊲ ⊔ 0 1

δ(p, σ) (s, ⊲, →) (s, 0, →) (s, 1, →) (q, ⊔, ←) (h, ⊲, →) (q, ⊔, −) (q0 , ⊔, →) (q1 , ⊔, →) (h, ⊲, →) (s, 0, ←) (s, 0, ←) (s, 0, ←) (h, ⊲, →) (s, 1, ←) (s, 1, ←) (s, 1, ←)

s s s s s q q0 s q q1 s q q0 s q h

´ ´ Pelda futas ⊲010 ⊲010 ⊲010 ⊲010 ⊲010⊔ ⊲010⊔ ⊲01 ⊔ ⊔ ⊲01⊔0 ⊲01 ⊔ 0 ⊲0 ⊔ ⊔0 ⊲0⊔10 ⊲0 ⊔ 10 ⊲ ⊔ ⊔10 ⊲⊔010 ⊲ ⊔ 010 ⊲⊔010 18 / 184

´ ok ´ Konfiguraci

Defin´ıcio´ ´ ıtasi ´ folyamat adott pillanatanak ´ ´ at ´ A szam´ teljes le´ıras ´ onak ´ konfiguraci nevezzuk. ¨ ´ ´ ahol Formalisan: egy (q, w, u) harmas, ◮

q ∈ K ∪ {,,igen”, ,,nem”, h}; ´ ol ´ balra eso˝ szo, ´ beleertve ´ w ∈ Σ+ , a mutatot azt a betut ˝ is, ¨ amelyet a mutato´ kijelol;

◮

´ ol ´ jobbra lev ´ o, ˝ esetleg ures ´ u ∈ Σ∗ , a mutatot ¨ szo.

◮


19 / 184

´ ´ o´ Atmenetrel aci M

´ (q, wσ, u) −→(q′ , w′ , u′ ) Defin´ıcio: ´ q ∈ K, δ(q, σ) = (q′ , ρ, D) es ′ ◮ D = ← eseten ´ w = w es ´ u′ = ρu; ◮ D = − eseten ´ w′ = wρ es ´ u′ = u; ◮

´ D = → eseten u1 ha u = τ u1 wρτ ha u = τ u1 ′ ′ u = w = ε ha u = ε wρ⊔ ha u = ε

Defin´ıcio´

Mk

M∗

´ (q, wσ, u) −→(q′ , w′ , u′ ), (q, wσ, u) −→(q′ , w′ , u′ ) a szokasos ´ modon.


20 / 184

´ altal ´ ´ ıtott fuggv ´ A Turing-gep kiszam´ ¨ eny

Defin´ıcio´ Legyen x ∈ (Σ − {⊲, ⊔})∗ . M(x) = M∗

,,igen” ha (s, ⊲, x) −→(,,igen”, w, u) valamely w, u szavakra; M∗

,,nem” ha (s, ⊲, x) −→(,,nem”, w, u) valamely w, u szavakra; M∗

y ha (s, ⊲, x) −→(h, w, u) valamely w, u szavakra ugy, ´ hogy ´ y nem ⊔-ra vegz ´ odik; ˝ wu = ⊲y⊔k alaku´ es ¨ ´ meg az (s, ⊲, x) ր kul ¨ onben, azaz ha M nem all ˝ ´ ob ´ ol ´ ind´ıtva. kezdokonfigur aci


21 / 184

´ novel ¨ es ´ Binaris

p∈K s s s s q q q


σ∈Σ ⊲ 0 1 ⊔ ⊲ 0 1

δ(p, σ) (s, ⊲, →) (s, 0, →) (s, 1, →) (q, ⊔, ←) (h, ⊲, →) (h, 1, −) (q, 0, ←)

´ ´ 1. Pelda futas (s, ⊲, 11011) (s, ⊲1, 1011) (s, ⊲11, 011) (s, ⊲110, 11) (s, ⊲1101, 1) (s, ⊲11011, ε) (s, ⊲11011⊔, ε) (q, ⊲11011, ⊔) (q, ⊲1101, 0⊔) (q, ⊲110, 00⊔) (h, ⊲111, 00⊔)

´ ´ 2. Pelda futas (s, ⊲, 111) (s, ⊲1, 11) (s, ⊲11, 1) (s, ⊲111, ε) (s, ⊲111⊔, ε) (q, ⊲111, ⊔) (q, ⊲11, 0⊔) (q, ⊲1, 00⊔) (q, ⊲, 000⊔) (h, ⊲0, 00⊔)

22 / 184

´ eldont ¨ ese ´ A palindromak

p∈K s s s s q0 q0 q0 q1 q1 q1


σ∈Σ ⊲ 0 1 ⊔ 0 1 ⊔ 0 1 ⊔

δ(p, σ) (s, ⊲, →) (q0 , ⊲, →) (q1 , ⊲, →) (,,igen”, ⊔, −) (q0 , 0, →) (q0 , 1, →) (q′0 , ⊔, ←) (q1 , 0, →) (q1 , 1, →) (q′1 , ⊔, ←)

p∈K q′0 q′0 q′0 q′1 q′1 q′1 q q q

σ∈Σ 0 1 ⊲ 0 1 ⊲ 0 1 ⊲

δ(p, σ) (q, ⊔, ←) (,,nem”, 1, −) (,,igen”, ⊲, →) (,,nem”, 0, −) (q, ⊔, ←) (,,igen”, ⊲, →) (q, 0, ←) (q, 1, ←) (s, ⊲, →)

23 / 184

´ Turing-gepek mint algoritmusok ւ ¨ ese ´ Nyelvek eldont

ց ´ uggv ´ ´ ıtasa ´ Szof ¨ enyek kiszam´

Defin´ıcio´ ¨ az L ⊆ (Σ − {⊲, ⊔})∗ ´ eldonti Azt mondjuk, hogy az M Turing-gep ´ ´ nyelvet, ha barmely x ∈ (Σ − {⊲, ⊔})∗ szora: x ∈ L ⇒ M(x) = ,,igen” x∈ / L ⇒ M(x) = ,,nem”

Defin´ıcio´ ´ felismeri az Azt mondjuk, hogy az M Turing-gep ´ ´ L ⊆ (Σ − {⊲, ⊔})∗ nyelvet, ha barmely x ∈ (Σ − {⊲, ⊔})∗ szora: x ∈ L ⇒ M(x) = ,,igen” x∈ / L ⇒ M(x) =ր


[x ∈ / L ⇒ M(x) 6= ,,igen”]

24 / 184

Defin´ıcio´ ¨ ˝ Egy L ⊆ (Σ − {⊲, ⊔})∗ nyelvet rekurz´ıvnak vagy eldonthet onek ´ ´ mely eldonti ¨ az L nevezunk, ¨ ha letezik olyan M Turing-gep, nyelvet. ´ ´ Rekurz´ıvan felsorolhatonak nevezzuk ¨ az L nyelvet, ha letezik ´ amely felismeri L-et. olyan Turing-gep,

´ ıtas ´ All´ ´ Minden rekurz´ıv nyelv rekurz´ıvan felsorolhato. ´ u´ implikaci ´ o´ nem igaz.) (A ford´ıtott irany

Defin´ıcio´ Legyen f : (Σ − {⊲, ⊔})∗ → Σ∗ . Azt mondjuk, hogy f rekurz´ıv ´ ´ ´ hogy barmely ´ fuggv ¨ eny, ha letezik olyan M Turing-gep, ∗ ´ M(x) = f (x). x ∈ (Σ − {⊲, ⊔}) szora


25 / 184

´ ak ´ Peld ´ ak ´ eldonthet ¨ Peld o˝ nyelvekre ◮

´ a {0, 1} ab ´ ec ´ e´ fol ¨ ott; ¨ palindromak

◮

{0n c0m c0n+m : n, m ≥ 0};

◮

{0n c0m c0nm : n, m ≥ 0};

◮

{0n c02 : n ≥ 0};

◮

¨ az x szam ´ binaris ´ {x1 cx2 cx1 + x2 : x1 , x2 ≥ 0}, ahol x jeloli ´ alakjat;

◮

´ {x : x pr´ımszam}.

n

´ ak ´ rekurz´ıv fuggv ´ Peld ¨ enyekre ◮

x 7→ ⊔x

x ∈ {0, 1}∗ ;

◮

x 7→ x + 1

x ≥ 0;

◮

xcy 7→ x + y

x, y ≥ 0;

◮

n 7→ pn

´ n ≥ 0, pn := az n. pr´ımszam.


26 / 184

◮

¨ esi ´ problem ´ ak ´ Nyelvek – eldont

◮

¨ esi ´ Rekurz´ıv nyelvek – algoritmikusan megoldhato´ eldont ´ ak ´ problem

◮

´ uggv ´ ´ asi ´ problem ´ ak ´ Szof ¨ enyek – optimalizal ´ Rekurz´ıv fuggv ¨ enyek – algoritmikusan megoldhato´ ´ asi ´ problem ´ ak ´ optimalizal

◮

´ ´ Barmely veges matematikai objektum (algoritmikusan) ´ kodolhat o´ szavakkal. ´ kapcsolatban ´ ´ ,,elfogadhato” ´ kodol ´ as ´ polinomialis Barmely ket ´ egymassal. ´ all ´ ıthatos ´ ag ´ es ´ bonyolultsag ´ elmelete ´ A kiszam´ fuggetlen ¨ a ´ ast ´ ol. ´ kodol


27 / 184

¨ ´ Tobbszavas Turing-gepek Defin´ıcio´ ´ egy M = (K, Σ, δ, s) rendszert Egy k szavas Turing-gepen ´ unk, ¨ ons ¨ eges ´ ´ ert ¨ ahol K, Σ, s ugyanazok, mint koz Turing-gep ´ eseten, δ pedig K × Σk → (K ∪ {h, ,,igen”, ,,nem”}) × (Σ × {←, −, →})k ´ ´ lekepez es. ¨ es: ´ ⊲ nem ´ırhato´ at ´ es ´ ,,nem lephet ´ ´ Kikot o˝ at”.

Defin´ıcio´ ´ o: ´ (q, w1 , u1 , . . . , wk , uk ), q ∈ K ∪ {h, ,,igen”, ,,nem”}, Konfiguraci wi ∈ Σ+ , ui ∈ Σ∗ . M

Mt

M∗

´ ok ´ ertelem ´ ´ Az −→, −→, −→ relaci szerint definialtak.


28 / 184

´ eldont ¨ ese ´ ket ´ szalaggal Palindromak

p s s s s q q q p p p p p ´ ´ Bonyolultsagelm elet

σ1 ⊲ 0 1 ⊔ 0 1 ⊲ 0 1 0 1 ⊔

σ2 ⊲ ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ 0 1 1 0 ⊲

δ(p, σ1 , σ2 ) (s, ⊲, →, ⊲, →) (s, 0, →, 0, →) (s, 1, →, 1, →) (q, ⊔, ←, ⊔, −) (q, 0, ←, ⊔, −) (q, 1, ←, ⊔, −) (p, ⊲, →, ⊔, ←) (p, 0, →, 0, ←) (p, 1, →, 1, ←) (,,nem”, 0, −, 1, −) (,,nem”, 1, −, 0, −) (,,igen”, ⊔, −, ⊲, →)

´ ´ Pelda futas (s, ⊲, 010, ⊲, ε) (s, ⊲010⊔, ε, ⊲010⊔, ε) (q, ⊲010, ⊔, ⊲010⊔, ε) (q, ⊲, 010⊔, ⊲010⊔, ε) (p, ⊲0, 10⊔, ⊲010, ⊔) (p, ⊲01, 0⊔, ⊲01, 0⊔) (p, ⊲010, ⊔, ⊲0, 10⊔) (p, ⊲010⊔, ε, ⊲, 010⊔) (,,igen”, ⊲010⊔, ε, ⊲0, 10⊔)

29 / 184

Defin´ıcio´ Legyen x ∈ (Σ − {⊔, ⊲})∗ . ◮

M(x) = ,,igen”, ha M∗

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(,,igen”, w1 , u1 , . . . , wk , uk ); ◮

M(x) = ,,nem”, ha M∗

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(,,nem”, w1 , u1 , . . . , wk , uk ); M∗

◮

M(x) = y, ha (s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(h, w1 , u1 , . . . , wk , uk ) ´ y a wk uk szo´ elejen ´ all ´ o´ ⊲ es ´ a veg ´ en ´ esetleg elofordul ˝ es o´ ´ aval ´ ´ ⊔ jelek elhagyas kapott szo;

◮

¨ M(x) =ր, kul ¨ onben.

¨ es, ´ felismeres ´ stb. koz ¨ ons ¨ eges ´ ´ Eldont Turing-gepekhez ´ hasonloan.


30 / 184

˝ ´ Idokorl at Defin´ıcio´ ¨ ´ M f (n) Legyen f : N → N, M pedig tobbszavas Turing-gep. ˝ ´ ´ ha M minden x bemeneten legfeljebb idokorl atos Turing-gep, ´ esben ´ ´ (|x| az x szo´ hosszat ´ jeloli.) ¨ f (|x|) lep megall. ´ elnevezes: ´ M idoig ˝ enye ´ Mas (legfeljebb) f (n).

Defin´ıcio´ ˝ ´ ¨ o˝ Turing-gep}. ´ TIME(f (n))= {L : ∃M f (n) idokorl atos L-et eldont

´ Pelda ◮ ◮ ◮

´ Ekkor: L ⊆ {0, 1}∗ , palindromak. L ∈ TIME (n+1)(n+2) ; 2 L ∈ TIME(3n + 3).

˝ ´ eseten ´ mindig kikotj ¨ uk, Idokorl at ¨ hogy f (n) > n.


31 / 184

´ szimulal ´ asa ´ egyszavassal k-szavas gep ´ Tetel ´ ˝ ´ ´ Barmely k-szavas f (n) > n idokorl atos M Turing-gephez ˝ ´ egyszavas megadhato´ vele ekvivalens O((f (n))2 ) idokorl atos ′ ´ M Turing-gep. Ekvivalens: M ′ (x) = M(x) minden x-re.

´ Bizony´ıtas ◮ ◮ ◮ ◮ ◮ ◮

´ ´ ´ ´ oj ´ at. ´ M ′ egyetlen szoban tarolja M k szavanak konkatenaci ´ Minden egyes szoban egy betu˝ ,,ala´ van huzva”. ´ ´ es ´ szimulal ´ as ´ ahoz ´ ´ ´ szot. ´ Egy lep M ′ vegigolvassa az egesz ´ ´ Esetleg jobbra lepteti a szot. ˝ eny ´ lep ´ esenk ´ ´ O(f (n)). Idoig ent ˝ eny: ´ Teljes idoig O((f (n))2 ).


32 / 184

´ felgyors´ıtas ´ Linearis

´ Tetel ´ Tegyuk ¨ fel, hogy L ∈ TIME(f (n)). Ekkor minden ǫ > 0 valos ′ ′ ´ szamra L ∈ TIME(f (n)) is teljesul, ¨ ahol f (n) = ǫf (n) + n + 2.

´ Bizony´ıtas ˝ ´ ´ Legyen M k-szavas, f (n) idokorl atos Turing-gep. k ha k > 1 k′ = 2 ha k = 1 ´ ´ ˝ ´ Belatjuk, hogy M szimulalhat o´ k′ -szavas, f ′ (n) idokorl atos ′ ´ Turing-geppel (M -vel).


33 / 184

´ felgyors´ıtas ´ Linearis

◮

◮

◮ ◮ ◮

◮ ◮

´ minden M ′ az M szavait m hosszu´ blokkokra bontja, es ´ tarol. ´ ˝ ent blokkot egyetlen betuk ¨ or´ ¨ ıtes. ´ M ′ masodik ´ ´ ´ ıti az Elso˝ menet: tom szavaban elkesz´ ¨ or´ ¨ ıtett valtozat ´ ´ n + 2 lep ´ es. ´ elso˝ szo´ (bemenet) tom at: ´ es. ´ ´ ´ mozgatja a mutatot: ´ ⌈ mn ⌉ lep A masodik szo´ elejere ′ ´ (q, i1 , . . . , ik ), 1 ≤ ij ≤ m. M allapotai: ´ lm egym ´ kovet ¨ o˝ lep ´ es ´ et ´ 6 lep ´ esben ´ M ′ az M gep m ast f (n) ´ ´ es. ´ szimulalja: 6 m lep l m l m f (n) ˝ eny: ´ Teljes idoig n + 2 + ⌈ mn ⌉ + 6 f (n) ≤ n + 2 + 7 m m . ´ nagy, akkor ez ≤ ǫf (n) + n + 2. Ha m eleg


34 / 184

´ A P osztaly ¨ ´ Kovetkezm eny ◮

◮

Ha L ∈ TIME(f (n)), ahol f (n) = an + b, a, b ∈ N, a > 0, ´ at ´ tetszolegesen ˝ ¨ akkor n egyutthat ¨ oj kozel vihetjuk ¨ 1-hez: L ∈ TIME(f ′ (n)), ahol f ′ (n) = (1 + ǫ)n + c, valamely ˝ ´ valamely c-re. tetszolegesen kicsi pozit´ıv ǫ-ra es ´ Ha L ∈ TIME(f (n)), ahol f (n) masodfok u´ polinom, akkor a ´ ´ at ´ tetszolegesen ˝ ¨ masodfok u´ tag egyutthat ¨ oj kozel vihetjuk ¨ 0-hoz.

Defin´ıcio´ P = TIME(nk ), azaz P =

∞ S

TIME(ni ).

i=1

´ L ∈ P ⇔ ∃p(n) polinom, hogy L ∈ TIME(p(n)). Tehat ´ ´ Bonyolultsagelm elet

35 / 184

´ ´ Tarkorl atok Defin´ıcio´ ´ olyan Legyen k > 2. Egy k-szavas lyukszalagos Turing-gep ´ mely k-szavas Turing-gep, ◮ elso ˝ szalagjat ´ csak olvassa, ´ csak ´ır. utolso´ szalagjara ´ szinonimaja.) ´ (itt a ,,szalag” a ,,szo” ◮

´ Dk 6= ←. δ(q, σ1 , . . . , σk ) = (p, ̺1 , D1 , . . . , ̺k , Dk ) ⇒ σ1 = ̺1 es ´ a´ ha σ1 = ⊔, akkor D1 = ←. Tovabb

´ ıtas ´ All´ ´ ˝ ´ ´ Barmely k-szavas f (n) idokorl atos M Turing-gephez ´ ˝ ˝ ´ elkesz´ıtheto egy vele ekvivalens, O(f (n)) idokorlatos ′ ´ (k + 2)-szavas lyukszalagos M Turing-gep.


36 / 184

´ eny ´ Tarig Defin´ıcio´ ´ es ´ x egy bemeno˝ szo. ´ Legyen M egy k-szavas Turing-gep Tegyuk ¨ fel, hogy M∗

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(p, w1 , u1 , . . . , wk , uk ), ahol p ∈ {,,igen”, ,,nem”, h}. k P ´ enye ´ x-en |wi ui |. Ekkor M tarig i=1

´ Kiveve, ha M (hangsulyozottan) ´ lyukszalagos. k−1 P ´ eny: ´ Ekkor a tarig |wi ui |. i=2

Defin´ıcio´ ´ eny ´ u˝ Turing-gep, ´ ha M Azt mondjuk, hogy M egy f (n) tarig ´ es ´ tarig ´ enye ´ minden x bemeneten megall minden x bemeneten legfeljebb f (|x|). ´ ´ Bonyolultsagelm elet

37 / 184

´ ´ osztalyok ´ Tarbonyolults agi Defin´ıcio´ ´ Azt mondjuk, hogy az L nyelv a SPACE(f (n)) bonyolultsagi ´ ´ ¨ o, ˝ f (n) tarkorl ´ ´ osztalyban van, ha letezik az L nyelvet eldont atos ´ lyukszalagos Turing-gep.

¨ es ´ Jelol L = SPACE(log n)

´ Pelda ´ nyelve az L osztalyba ´ A palidromak esik. ◮ Egy lyukszalagos Turing-gep ´ masodik ´ ´ szavaban egy ´ binaris ´ alakjat ´ tarolja. ´ 1 ≤ i ≤ n szam ◮

´ hogy a bemenet i-dik betuje Az i-edik menetben megnezi, ˝ ´ ´ ´ ´ ´ ´ megegyezik-e a hatulrol i-dik betuj ˝ evel. A szamlalashoz ´ hasznal. ´ egy harmadik munkaszot


38 / 184

´ tar ´ osszeh ¨ ´ Linearis uz ´ as ´ Tetel L ∈ SPACE(f (n)) ⇒ ∀ǫ > 0 : L ∈ SPACE(ǫf (n)).

´ Bizony´ıtas ¨ o˝ f (n) tarkorl ´ ´ Legyen M az L-et eldont atos lyukszalagos ´ Legyen m > 0. Kesz´ ´ ıtunk ´ o´ M ′ Turing-gep. ¨ egy M-et szimulal ´ lyukszalagos Turing-gepet, mely M munkaszalagjait m-es ´ l megyetlen munkaszalagjan. ´ blokkokban tarolja f (n) ′ ´ enye: ´ M tarig m . l m De f (n) ≤ ǫf (n), ha m ≥ 1ǫ . m


39 / 184

´ Nemdeterminisztikus Turing-gep Defin´ıcio´ ´ egy N = (K, Σ, ∆, s) k-szavas nemdeterminisztikus Turing-gep ´ s ugyanazok, mint koz ¨ ons ¨ eges ´ rendszer, ahol K, Σ es k-szavas ´ eseten, ´ es ´ Turing-gep k ∆ ⊆ K × Σ × (K ∪ {,,igen”, ,,nem”, h}) × (Σ × {←, −, →})k . N

´ o, ´ kozvetlen ¨ ´ ´ eses ´ ´ atmenet (−→), t lep atmenet A konfiguraci Nt

N∗

¨ ´ ´ okat ´ ˝ oeknek ˝ (−→), kozvetett atmenet (−→) relaci az eloz ˝ definialjuk. ´ megfeleloen


(p, w1 , u1 , . . . , wk , uk )

→ ց

(p′ , w′1 , u′1 , . . . , w′k , u′k ) (p′′ , w′′1 , u′′1 , . . . , w′′k , u′′k ) 40 / 184

Defin´ıcio´ ¨ az L Legyen L ⊆ (Σ − {⊲, ⊔})∗ . Azt mondjuk, hogy N eldonti ´ nyelvet, ha minden x ∈ (Σ − {⊲, ⊔})∗ szora: x ∈ L ⇐⇒ ∃w1 , u1 , . . . , wk , uk : N∗

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(,,igen”, w1 , u1 , . . . , wk , uk )

´ nem kovetelj ¨ Tehat uk ¨ meg, hogy N minden bemeneten ´ ´ letezhetnek ´ ´ ´ ıtasi ´ sorozatok is! megalljon es vegtelen szam´

Defin´ıcio´ Legyen L ⊆ (Σ − {⊲, ⊔})∗ , f : N → N. Azt mondjuk, hogy N f (n) ¨ ´ valahanyszor ´ ´ ˝ ¨ L-t, ha eldonti, es egy x szora, idoben eldonti ´ ´ (q, w1 , u1 , . . . , wk , uk ) konfiguraci ´ ora: ´ t ≥ 0 szamra es Nt

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(q, w1 , u1 , . . . , wk , uk ), ´ hogy t ≤ f (|x|). mindig fennall, ´ minden szam´ ´ ıtasi ´ sorozat veges. ´ Tehat


41 / 184

´ Az NTIME(f (n)) osztalyok Defin´ıcio´ ´ ˝ ¨ o˝ NTIME(f (n)) = { L : letezik L-t f (n) idoben eldont ´ nemdeterminisztikus Turing-gep}. Itt is feltesszuk, ¨ hogy f (n) > n.

´ ıtas ´ All´ TIME(f (n)) ⊆ NTIME(f (n)).

´ Tetel ´ szamra ´ Minden ǫ > 0 valos NTIME(f (n)) ⊆ NTIME(ǫf (n) + n + 2).


42 / 184

´ Az NP osztaly Defin´ıcio´ NP = NTIME(nk ) =

∞ [

NTIME(ni ).

i=1

´ Pelda TSP(E) ∈ NP.

´ ınutlen), ´ ´ Nem ismert (de nagyon valosz´ ˝ hogy letezik-e modszer ´ ´ ´ as ´ ara. ´ nemdeterminisztikus Turing-gepek ,,hatekony” szimulal ?

P = NP ´ ´ Bonyolultsagelm elet

43 / 184

´ ´ asa ´ Nemdeterminisztikus gepek szimulal ´ Tetel NTIME(f (n)) ⊆

[

TIME(cf (n) ).

c>1

´ Bizony´ıtas ˝ ´ Legyen N = (K, Σ, ∆, s) egy f (n) idokorl atos ´ nemdeterminisztikus Turing-gep. ´ ´ ˝ ´ Belatjuk, hogy N szimulalhat o´ egy 3-szavas, cf (n) idokorl atos ´ ´ (determinisztikus) M Turing-geppel valamely c > 1 szamra. ´ Minden (q, σ) ∈ K × Σ rendezett parra legyen Cq,σ

=

{(q′ , σ ′ , D) : ((q, σ), (q′ , σ ′ , D)) ∈ ∆},

d

=

max |Cq,σ |. q,σ

˝ hogy d > 1. Felteheto,


44 / 184

◮

◮

◮

◮

´ esb ´ ol ˝ all ´ o´ nemdeterminisztikus valaszt ´ ´ Minden t lep asi ´ sorozat reprezentalhat o´ egy c1 . . . ct , ci ∈ {0, . . . , d − 1} sorozattal. A sorozatokat rendezzuk ¨ lexikografikusan. ´ sorra elo˝ all´ ´ ıtja a c1 . . . ct M az egyik munkaszalagjan ´ ´ sorozatokat, a masikon ´ valaszt asi az adott sorozatra ´ N muk ¨ es ´ et. ´ szimulalja ˝ od ´ meg ,,igen” allapotban, ´ ´ ´ M akkor all ha valamely valaszt asi sorozatra N ugyanezt teszi. ´ meg ,,nem” allapotban, ´ ´ N M akkor all ha valamely t eseten ¨ ´ ´ sorozatra egy ,,igen”-tol ˝ az osszes t hosszu´ valaszt asi ¨ oz ¨ o˝ allapotban ´ ´ meg. kul ¨ onb all

˝ eny: ´ Idoig ´ ´ ´ Valaszt asok szama:

fP (n) t=0

dt =

df (n)+1 −1 d−1

´ Sorozatonkent: O(f (n)). f (n) ¨ Osszesen: O(f (n)df (n) ) = O(d1 ).


= O(df (n) ).

45 / 184

´ Az NSPACE(f (n)) osztalyok Defin´ıcio´ Azt mondjuk, hogy a k-szavas N = (K, Σ, ∆, s) ´ f (n) tarral ´ nemdeterminisztikus lyukszalagos Turing-gep (vagy ¨ az L ⊆ (Σ − {⊲, ⊔})∗ nyelvet, ha eldonti, ¨ ´ ´ ´ eldonti es tarkorl attal) ´ valahanyszor N∗

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→ (q, w1 , u1 , . . . , wk , uk ), ahol x ∈ (Σ − {⊲, ⊔})∗ , q ∈ K ∪ {,,igen”, ,,nem”, h}, wi , ui ∈ Σ∗ , ´ hogy fennall, k−1 X

|wi ui | ≤ f (|x|).

i=2

Defin´ıcio´ ´ ´ NSPACE(f (n)) = {L : letezik olyan nemdeterminisztikus Turing-gep, ´ ¨ L-et}. mely f (n) tarral eldonti


46 / 184

NL

Defin´ıcio´ NL = NSPACE(log n).

´ ´ ´ ´ ıtasi ´ sorozata is! A Turing-gepnek letezhet vegtelen szam´

´ ıtas ´ All´


SPACE(f (n)) ⊆ NSPACE(f (n)).

47 / 184

˝ EG ´ ´ ELERHET OS ´ Pelda ˝ EG ´ ´ ∈ NL. ELERHET OS

´ Bizony´ıtas ◮

◮

◮

◮

´ 4-szavas lyukszalagos nemdeterminisztikus Turing-gepet tervezunk. ¨ ´ csucs ´ alakja Egyik munkaszalag: i aktualis ´ binaris (kezdetben 1). ´ ´ a gep ´ Masik munkaszalag: nemdeterminisztikusan general ´ egy j csucsot ´ (binarisan). ˝ ´ Ellenorzi, hogy (i, j) el-e. ◮ ◮

◮

´ ´ Ha nem, akkor ,,nem” allapotban megall. Ha igen, akkor ´ ,,igen” allapotban ´ ´ j = n eseten megall; ´ kicsereli ´ i-t j-vel es ´ folytatja az eljar ´ ast. ´ j 6= n eseten

´ Az ,,igen” valaszt az output szalagra ki´ırja.


48 / 184

´ Megjegyzes ´ obb ˝ azt is belatjuk, ´ Kes hogy ˝ EG ´ ´ ∈ SPACE(log2 (n)). ELERHET OS

´ Tetel


∀ǫ > 0 : NSPACE(f (n)) ⊆ NSPACE(ǫf (n)).

49 / 184

¨ ´ er ´ es ´ u˝ gepek ´ Kozvetlen hozzaf (RAM)

´ ˝ bizony´ıteka: ´ legfobb az A Church-Turing tezis ´ ´ matematikai modellje algoritmusfogalom barmely ket ekvivalens.

˝ ´ Erosebb tezis ´ idoig ˝ eny ´ uk ¨ okkel ¨ ,,Az algoritmusok es ¨ matematikai eszkoz valo´ ´ ere ´ tett barmely ´ ´ ´ ´ eppen ´ modellezes esszer u˝ k´ıserlet szuks ¨ egk ´ idoig ˝ eny-fogalomhoz ´ olyan modellhez es vezet, mely ´ ´ polinomialisan ekvivalens a Turing-geppel.” ´ ´ Ezt demonstraljuk RAM eseten.


50 / 184

RAM

◮

◮

◮

´ kezdve Adatszerkezet: regiszterek, melyek 0-tol ´ ˝ sorszamozottak. Minden regiszter tetszoleges (pozit´ıv ´ szamot ´ ´ vagy negat´ıv) egesz tarolhat. A 0. regiszter: ´ akkumulator. ´ modok: ´ C´ımzesi direkt: j indirekt: ↑ j ¨ kozvetlen: =j ´ ´ al ´ o: ´ κ utas´ıtassz aml

´ szamok ´ bemenet: (i0 , i1 , . . . , it ) egesz sorozata ´ rj jeloli. ¨ A j. regiszter tartalmat ◮


51 / 184

´ Utas´ıtasok

READ j READ ↑ j STORE j STORE ↑ j ´ x ∈ {j, ↑ j, = j} eseten LOAD x ADD x SUB x HALF JUMP j JZERO j JPOS j JNEG j HALT


r0 r0 rj rrj

:= ij := irj := r0 := r0

r0 := x r0 := r0 + x r0 := r0 − x r0 := ⌊r0 /2⌋ κ := j ha r0 = 0, akkor κ := j ha r0 > 0, akkor κ := j ha r0 < 0, akkor κ := j

52 / 184

˝ eny ´ RAM idoig ´ ´ ´ at ´ Program: Utas´ıtasok veges sorozata. A program szemantikaj ´ ´ ´ ´ utas´ıtas ´ a program termeszetes modon definialjuk. Hibas ¨ es ´ enek ´ ´ as ´ at ´ eredmenyezi. ´ muk ˝ od terminal

˝ eny ´ szam´ ´ ıtasa ´ Idoig ´ egysegnyi ´ Minden utas´ıtas ´ – nem Tulzottan ´ liberalis

´ Bemenet merete ´ I = (i0 , i1 , . . . , it ) merete: ℓ(I) =

t P

ℓ(ij ).

j=0

´ binaris ´ reprezentaci ´ oj ´ anak ´ ℓ(ij ) az ij szam hossza. ´ O(n) idoig ˝ eny ´ azt jelenti, hogy a lep ´ essz ´ ´ aranyos ´ Tehat am a ´ ´ bemeneten adott szamok logaritmusaval. ´ ´ Bonyolultsagelm elet

53 / 184

´ Tetel ´ polinomialisan ´ A Turing-gep ekvivalens a RAM-mal. ´ B Pontosabban: A es

A ˝ ´ ´ Legyen L ⊆ (Σ − {⊲, ⊔})∗ a T, f (n) idokorl atos Turing-geppel ¨ ott ¨ nyelv. Legyen Σ = {σ1 , . . . , σk } es ´ eldont DΣ = {(i1 , . . . , in , 0) : n ≥ 0, 1 ≤ ij ≤ k}. ´ DΣ a Σ∗ -nak felel meg.) (Tehat Legyen ϕL : DΣ → {0, 1}

ϕL (i1 , . . . , in , 0) = 1 ⇐⇒ σi1 . . . σin ∈ L.

´ ˝ Ekkor letezik olyan RAM-program, mely O(f (n)) idoben ´ ıtja ϕL -t. kiszam´


54 / 184

B ´ szamok ´ ´ Legyen D egesz veges sorozatainak halmaza, ϕ pedig ´ szamok ´ ´ kepez ´ ´ D-t az egesz halmazaba o˝ fuggv ¨ eny. Adott i ´ ¨ b(i) az i szam ´ binaris ´ reprezentaci ´ oj ´ at, ´ egeszre jelolje ´ pedig legyen I = (i0 , i1 , . . . , it ) eseten b(I) = b(i0 ); b(i1 ); . . . ; b(it ). ´ ıthato´ RAM programmal”, akkor letezik ´ Ha ϕ ,,kiszam´ olyan M ´ mely kiszam´ ´ ıtja ϕ-t a kovetkez ¨ ´ Turing-gep, o˝ ertelemben: ˝ ´ M(b(I)) = b(ϕ(I)). tetszoleges I ∈ D eseten ´ a, ´ ha ϕ f (n) lep ´ esben ´ ´ ıthato´ RAM programmal, Tovabb kiszam´ 3 ´ ıthato´ O((f (n) ) idokorl ˝ ´ ´ akkor kiszam´ atos Turing-geppel.


55 / 184

´ Turing-gep ´ Univerzalis

´ Tetel ´ ´ amelynek ha adott egy M Letezik olyan U Turing-gep, ´ ´ Turing-gep es annak egy x bemenete, ugy ´ viselkedik, mint M az x-en, vagyis U(M; x) = M(x). ´ ´ x kodolva ´ ´ ara, ´ ´ U az Termeszetesen M es adottak U szam es ´ as ´ szerint szam´ ´ ıtja ki. M(x)-et ezen kodol


56 / 184

´ as ´ A kodol

˝ hogy M = (K, Σ, δ, s). Felteheto, Σ = {1, 2, . . . , |Σ|} K = {|Σ| + 1, . . . , |Σ| + |K|} s = |Σ| + 1

Így M megadhato´ a |K|, |Σ| szamok ´ ´ alakjaval, ´ binaris melyet δ ´ ¨ ´ le´ırasa kovet, amely ((q, σ), (p, ̺, D)) alaku´ parok sorozata. A q, ´ szammal ´ ´ A (, ), , stb. p, σ, ̺, D mindegyike binaris megadhato. ´ ´ binarisan. ´ karakterek is kodolhat ok ←, →, −, ,,igen”, ,,nem”, h ´ feleljen meg a |Σ| + |K| + 1, . . . , |Σ| + |K| + 6 szamoknak. Az x ´ megadhato´ binaris ´ szamok ´ ´ bemenet szinten sorozataval.


57 / 184

¨ ese ´ U muk ˝ od

´ ´ Ketszavas Turing-gep. ´ M; x bemenet 1. szo: ´ M aktualis ´ konfiguraci ´ oj ´ anak ´ ´ 2. szo: kodja ´ es ´ et ´ egy menetben szimulalja, ´ U az M minden lep melyben ◮ Vegigolvassa ´ ´ a 2. szot ◮

´ ´ elvegzend ´ ´ ot, ´ es ´ Meghatarozza a 2. szon o˝ transzformaci ´ azt elvegzi

´ U is azt teszi. Ha M megall, Amennyiben az U bemenete nem M; x alaku, ´ akkor (mondjuk) ´ vegtelen ciklusba esik.


58 / 184

´ asi ´ problema ´ A megall Defin´ıcio´ Legyen H = {M; x : M(x) 6=ր}.

´ Tetel ´ de nem rekurz´ıv. H rekurz´ıvan felsorolhato,


◮

´ ag: ´ az univerzalis ´ Turing-gep ´ Rekurz´ıvan felsorolhatos ´ es ´ eb ´ ol. ˝ letez ´ H nem rekurz´ıv: indirekt bizony´ıtas. ¨ ´ Tegyuk ¨ fel, hogy H eldonthet o˝ egy MH Turing-geppel. ´ melyre Legyen D olyan Turing-gep, D(M) = if MH (M; M) then ր else halt. Ekkor: D(D) =ր ⇔ MH (D; D) = ,,igen” ⇔ D(D) 6=ր, ´ ami ellentmondas.


59 / 184

´ AS ´ MEGALL ◮ ◮

´ x Adott: M es ´ es: ´ Megall-e ´ Kerd M az x-en?

´ AS ´ eldonthetetlen ¨ ´ MEGALL problema.

´ Megjegyzes ¨ ott: ¨ H teljes a rekurz´ıvan felsorolhato´ nyelvek koz ◮ H rekurz´ıvan felsorolhato ´ ◮ Minden rekurz´ıvan felsorolhato ´ nyelv (rekurz´ıvan) visszavezetheto˝ H-ra: ◮ ◮

´ altal ´ Legyen L az M Turing-gep felismert nyelv. x ∈ L ⇔ M; x ∈ H ?

◮


?

´ az x ∈ L kerd ´ es ´ eldont ¨ es ´ et ´ visszavezettuk Tehat ¨ az M; x ∈ H ´ esre. ´ kerd 60 / 184

´ ıtas ´ All´ ´ ´ ¨ Az alabbi problema algoritmikusan eldonthetetlen. ◮ Adott: M Turing-gep ´ ◮

´ es: ´ M megall-e ´ ´ Kerd minden bemeneten?

´ Bizony´ıtas ´ x eseten ´ legyen M ′ olyan Turing-gep, ´ hogy az M ′ Adott M es ´ minden y bemeno˝ szavara: M ′ (y) = M(x). Így ´ minden bemeneten. ´ M(x) 6=ր ⇔ M ′ megall ´ az adott problema ´ ¨ Ha tehat eldonthet o˝ lenne, akkor ´ AS ´ is az lenne. MEGALL


61 / 184

´ Rice tetele

´ Rice tetele ´ A rekurz´ıvan felsorolhato´ nyelvek egyetlen nemtrivialis ´ sem donthet ¨ tulajdonsaga o˝ el algoritmikusan.


62 / 184

´ ıtas ´ All´ Ha L rekurz´ıv, akkor L is az.

´ Bizony´ıtas ´ a ,,nem” allapotok ´ ´ es ´ evel. ´ Az ,,igen” es felcserel

´ ıtas ´ All´ ´ csak akkor rekurz´ıv, ha L es ´ L rekurz´ıvan Egy L nyelv akkor es ´ felsorolhatok.


◮

L rekurz´ıv ⇒ L rekurz´ıvan felsorolhato´ L rekurz´ıv ⇒ L rekurz´ıv, ´ıgy L rekurz´ıvan felsorolhato´ ´ Ekkor L ´ L rekurz´ıvan felsorolhatok. Tegyuk ¨ fel, hogy L es ´ felismerheto˝ egy M, L pedig egy M Turing-geppel. ´ ´ M-et parhuzamosan! ´ Szimulaljuk M-et es


63 / 184

coC

Defin´ıcio´ ´ Legyen C nyelvek egy osztalya. Ekkor coC = {L : L ∈ C}.

¨ es ´ Jelol


R = {L : L rekurz´ıv} ´ RE = {L : L rekurz´ıvan felsorolhato}

64 / 184

´ coRE viszonya R, RE es ¨ ´ Kovetkezm eny R = coR RE 6= coRE R = RE ∩ coRE coRE

RE R


65 / 184

´ aja ´ Hilbert 10. problem ◮

◮

Adott: f (x1 , . . . , xn ) = g(x1 , . . . xn ) diofantikus egyenlet, ahol ´ g egesz ´ egyutthat ´ polinomok. f es ¨ os ´ es: ´ Letezik-e ´ ´ ert ´ ek ´ u˝ megoldas? ´ Kerd egesz

´ (Matijaseviˇc) Tetel ´ aja ´ algoritmikusan megoldhatatlan. Hilbert 10. problem

´ problem ´ aja ´ Post megfelelkezesi ◮ ◮

Adott: u1 , v1 , . . . , un , vn ∈ Σ∗ . ´ es: ´ Letezik-e ´ Kerd olyan i1 , . . . , ik (k > 0, 1 ≤ ij ≤ n) sorozat, hogy ui1 . . . uik = vi1 . . . vik ?

´ (Post) Tetel ´ A fenti problema algoritmikusan megoldhatatlan.


66 / 184

´ Egy domino´ problema

◮ ◮

´ Adott: Domino´ t´ıpusok veges halmaza. ´ es: ´ Kirakhato-e ´ ezekkel a dominokkal ´ ´ s´ık Kerd az egesz ´ hezagmentesen?

u1 T´ıpus:

u3 ,

u2

ui ∈ Σ∗ .

u4 ´ nem forgathatoak. ´ A dominok

´ Tetel ´ A domino´ problema algoritmikusan megoldhatatlan.


67 / 184

´ Egy megoldatlan problema

◮ ◮

´ szam. ´ Adott: m pozit´ıv egesz ´ es: ´ Kongruens-e m? Kerd

´ azt kerdezz ´ ´ ´ ¨ u˝ Tehat uk, ¨ hogy letezik-e olyan dereksz og ´ ¨ mely oldalai racionalis ´ hosszus ´ uak ´ melynek haromsz og, ´ ag ´ es terulete ¨ m.

´ Pelda 1, 2, 3, 4 nem kongruensek. 5 kongruens (Fibonacci): 3 20 41 a= , b= , c= 2 3 6

´ ¨ ˝ Nem ismert, hogy a problema algoritmikusan eldonthet o-e.


68 / 184

´ osztalyok ´ Bonyolultsagi ´ osztaly ´ megadasa ´ Bonyolultsagi ◮ ◮ ◮ ◮

´ ıtasi ´ modell (altal ´ aban ´ szam´ nem tul ´ fontos) ´ ıtasi ´ mod ´ szam´ ´ ˝ ´ korlatozand o´ eroforr as ´ f :N→N korlat:

Defin´ıcio´ ´ fuggv ´ ´ megengedett bonyolultsagi ¨ eny, ha Az f (n) fuggv ¨ eny ¨ ˝ es ´ letezik ´ monoton nemcsokken o, olyan Mf k-szavas ´ mely O(n + f (n)) idoben ˝ ´ O(f (n)) lyukszalagos Turing-gep, es ´ ´ ıtja f -et a kovetkez ¨ ´ tarban kiszam´ o˝ ertelemben: Minden n hosszu´ x bemenetre Mft

(s, ⊲, x, ⊲, ε, . . . , ⊲, ε) −→(h, ⊲, x, ⊲, ⊔j1 , . . . , ⊲, ⊔jk−2 , ⊲⊓f (n) , ε), ´ ji = O(f (n)) csak n-tol ˝ fuggnek. ahol a t = O(f (n) + n) es ¨ ´ f (n) > n is kikot ¨ es! ´ Ido˝ eseten ´ ´ Bonyolultsagelm elet

69 / 184

´ ak ´ Peld ◮

´ Minden konstans fuggv ¨ eny.

◮

⌈log n⌉, 2n , n.

◮

f ,g ⇒ f + g, f · g, f g . ´ minden polinom. Tehat

◮

Defin´ıcio´ Egy M (lyukszalagos vagy nem, determinisztikus vagy ´ pontos, ha leteznek ´ ´ nemdeterminisztikus) Turing-gep olyan f es ´ ´ ´ g fuggv ¨ enyek, hogy M barmely n hosszu´ bemenetehez tartozo´ ´ a megall ´ as ´ ´ ıtasi ´ sorozata pontosan f (n) hosszu´ es szam´ ´ ´ eseteben ´ pillanataban M minden szava (lyukszalagos gep az ´ az utolso´ kivetel ´ evel) ´ pontosan g(n) hosszu. ´ elso˝ es


70 / 184

´ ıtas ´ All´ Tegyuk ¨ fel, hogy az M (determinisztikus vagy ´ f (n) idoben ˝ ´ nemdeterminisztikus) Turing-gep (vagy tarral) ¨ az L nyelvet, ahol f megengedett. eldonti ´ mely O(f (n)) idoben ˝ ´ Ekkor letezik olyan M ′ pontos Turing-gep, ´ ¨ el az L nyelvet. (vagy tarral) donti ´ M ′ meg ´ nemdeterminisztikus esetben is mindig megall!) ´ (Tehat

´ Bizony´ıtas ´ ıto” ´ M ′ egy adott n hosszu´ x bemeneten az ,,f (n)-t kiszam´ ´ szimulal ´ as ´ aval ´ ¨ es ´ et, ´ melynek veg ´ en ´ Turing-gep kezdi muk ˝ od f (n) ˝ ´ ´ egy munkaszalagon eloall az ⊓ szo. ˝ hogy minden tovabbi ´ Felteheto, munkaszalag hossza is ennyi ´ ´ az elso˝ fazis utan. ´ ido˝ eseten ´ az ⊓f (n) szot ´ mint or ´ at ´ hasznalva ´ Ezutan pontosan ´ esig ´ ´ M muk ¨ es ´ et ´ (esetleg ures ´ esekkel). ´ f (n) lep szimulalja ˝ od ¨ lep ´ eseten ´ valamely alkalmas c konstansra cf (n) lep ´ esig ´ Tar ´ M-et. szimulalja


71 / 184

¨ esek ´ Jelol

TIME( f (n) ), SPACE( f (n) ), P = TIME(nk ), PSPACE = SPACE(nk ), L = SPACE(log n), k EXP = TIME(2n )


NTIME( f (n) ) NSPACE( f (n) ) NP = NTIME(nk ) NPSPACE = NSPACE(nk ) NL = NSPACE(log n)

72 / 184

´ A hierarchia tetelek ´ Tetel ´ fuggv ´ Ha f (n) > n megengedett bonyolultsagi ¨ eny, akkor TIME(f (n)) ( TIME( (f (2n + 1))3 ).

´ Bizony´ıtas Legyen ´ esben ´ Hf = {M;x : M legfeljebb f (|x|) lep elfogadja x-et}, ˝ ¨ ´ ahol M tetszoleges tobbszavas Turing-gep. ´ ıtas: ´ Hf ∈ TIME( (f (n))3 ). All´ ´ ıtas: ´ Hf ∈ All´ / TIME( f (⌊n/2⌋) ).

´ Tetel ´ fuggv ´ Ha f (n) > n megengedett bonyolultsagi ¨ eny, akkor


TIME(f (n)) ( TIME( f (n) log2 (f (n)) ). 73 / 184

´ A hierarchia tetelek ´ Pelda 2

P ⊆ TIME(2n ) ( TIME( (22n+1 )3 ) ⊆ TIME(2n ) ⊆ EXP. ´ P ( EXP. Tehat

´ Tetel ´ fuggv ´ Ha f (n) ≥ n megengedett bonyolultsagi ¨ eny, akkor SPACE(f (n)) ( SPACE( f (n) log f (n) ).

´ Pelda L ⊆ SPACE(n) ( SPACE(n2 ) ⊆ PSPACE. ´ L ( PSPACE. Tehat


74 / 184

´ any ´ alapveto˝ osszef ¨ ´ bonyolultsagi ´ Neh ugg ¨ es ´ osztalyokra

´ Tetel ´ hasonloan ´ tarra ´ (a) TIME( f (n) ) ⊆ NTIME( f (n) ) es (b) NTIME( f (n) ) ⊆ SPACE( f (n) ) (c) NSPACE( f (n) ) ⊆ TIME( klog n+f (n) )

´ Bizony´ıtas ´ (a) trivialis.


75 / 184

NTIME( f (n) ) ⊆ SPACE( f (n) ) ˝ ´ ´ (b) Legyen M f (n) idokorl atos nemdeterminisztikus Turing-gep. ˝ hogy minden szam´ ´ ıtasi ´ sorozat f (n) lep ´ esb ´ ol ˝ all ´ n Felteheto, ´ minden nem megall ´ asi ´ hosszu´ x bemeneten, es ´ onak ´ ´ konfiguraci d > 0 ,,leszarmazottja” van. Így a ´ ´ sorozatokat reprezentalhatjuk ´ nemdeterminisztikus valaszt asi ´ az {1, . . . , d}f (n) halmaz elemeivel. M ′ ezeket generalja ´ a ,,tarat ´ ´ ´ lexikografikusan, es ujra ´ felhasznalva” szimulalja ¨ es ´ et. ´ minden sorozatra M muk ˝ od ´ ,,igen” allapotban, ´ ´ ´ M ′ megall ha M ,,igen” allapotban all meg. ´ meg ,,nem” allapotban, ´ M ′ akkor all ha M egyetlen ´ ´ sorozat eseten ´ sem allt ´ meg ,,igen” allapotban. ´ valaszt asi ´ ´ sorozatot Mivel f (n) megengedett, az elso˝ valaszt asi f (n) ´ tudjuk (1 ). generalni ´ eny: ´ Tarig f (n).


76 / 184

NSPACE( f (n) ) ⊆ TIME( klog n+f (n) ) ´ (c) bizony´ıtasa: ´ ¨ o˝ M legyen az L nyelvet f (n) tarral eldont ´ Mivel M lyukszalagos, az nemdeterminisztikus Turing-gep. ´ nincs szuks ´ utolso´ szalag tartalmara ¨ eg. ´ o: ´ Adott x, n-hosszu´ bemenethez tartozo´ konfiguraci (q, i, w2 , u2 , . . . , wk−1 , uk−1 ) f (n)

log n+f (n)

´ Ezek szama: . nc1 = c1 ´ es: ´ Elerhet ´ ˝ az x-hez tartoz konfiguraci ´ ob ´ ol ´ egy Kerd o-e ´ o? ´ (,,igen”,. . . ) alaku´ konfiguraci ˝ EG ´ ´ problema, ´ ´ idoben ˝ Ez az ELERHET OS mely linearis ´ Tehat ´ letezik ´ megoldhato. olyan c konstans, hogy L ¨ ´ ˝ eldonthet o˝ Turing-geppel clog n+f (n) idoben.


77 / 184

´ os ´ graf ´ elkesz´ ´ ıtheto˝ ,,elore” ˝ ´ A konfiguraci is, de szebb megoldas ´ eseten ´ az x bemenet es ´ M gep ´ ismereteben ´ az, hogy szuks ¨ eg ¨ uk ´ konfiguraci ´ o´ koz ¨ ott ¨ van-e eldontj ¨ minden esetben, hogy ket ´ el.

¨ ´ Kovetkezm eny L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP.

´ Bizony´ıtas L ⊆ NL

(a)

NL = NSPACE(log n) ⊆ TIME(klog n ) ⊆ P P ⊆ NP

(a)

NP = NTIME(nk ) ⊆ SPACE(nk ) = PSPACE nk

PSPACE = SPACE(nk ) ⊆ TIME(2 ) = EXP


(c) (b) (c) 78 / 184

Mivel P ( EXP, a P ⊆ NP, NP ⊆ PSPACE, PSPACE ⊆ EXP ´ valamelyike biztosan valodi. Mivel L ( PSPACE, az L ⊆ NL, NL ⊆ P, P ⊆ NP, ´ NP ⊆ PSPACE valamelyike biztosan valodi.

´ Sejtes Mindegyik az.


79 / 184

´ Savitch tetele ´ Tetel ˝ EG ´ ´ ∈ SPACE(log2 (n)). ELERHET OS

´ Bizony´ıtas ´ a csucsok ´ at, ´ akar ´ a szomszeds ´ agi ´ matrix ´ (Itt n akar ´ szam ´ as ´ ahoz ´ ´ ´ at ´ is jelolheti.) ¨ tarol szuks ¨ eges bitek szam ´ azt kerdezz ´ ´ ˝ n-be Legyen G egy n csucs ´ u´ graf, uk, ¨ letezik-e 1-bol ´ anosabban ´ ´ y0 -ba. vagy altal x0 -bol ´ ´ ˝ y-ba vezeto˝ UT(x, y, i) ⇔ letezik x-bol ´ u´ ut legfeljebb 2i hosszus ´ ag ´ ´ ´ csak akkor erhet ´ ´ ha Vilagos, hogy akkor es o˝ el y0 az x0 -bol, ´ UT(x , y , ⌈log n⌉). 0 0


80 / 184

´ ´ ıtasa ´ UT(x, y, i) szam´

i=0: ´ UT(x, y, 0) =

´ ,,igen” ha x = y vagy (x, y) el ¨ ,,nem” kul ¨ onben.

i>0: ´ ˝ ´ Ellenorizz uk ¨ minden z-re, hogy UT(x, z, i − 1) es ´ ´ UT(z, y, i − 1) igaz-e. Ha letezik ilyen z, akkor ´ ´ ¨ UT(x, y, i) = ,,igen”, kul ¨ onben UT(x, y, i) = ,,nem”.


81 / 184

´ ıthetunk ´ Kesz´ ¨ olyan 3-szavas lyukszalagos Turing-gepet, mely ´ ıtja. ezt az algoritmust megvalos´ ◮

1. szalag: G, x0 , y0 – bemenet

◮

´ lanc, ´ 2. szalag: verem, rekurz´ıv h´ıvasi kezdetben (x0 , y0 , ⌈log n⌉) ´ 3. szalag: valasz

◮

´ lanc ´ hossza: ⌈log n⌉ H´ıvasi Egy elem hossza: O(⌈log n⌉) ¨ ´ eny: ´ Osszes tarig O(log2 n)


82 / 184

¨ ´ Kovetkezm eny ´ fuggv ´ Ha f (n) ≥ log n megengedett bonyolultsagi ¨ eny, akkor NSPACE(f (n)) ⊆ SPACE( (f (n))2 ). ´ Specialisan: PSPACE = NPSPACE.

´ Bizony´ıtas ´ ´ Legyen N nemdeterminisztikus, f (n) tarkorl atos lyukszalagos ´ Az N egy x bemeneten ´ valo´ szimulal ´ as ´ ahoz ´ Turing-gep. ˝ o˝ algoritmust az N konfiguraci ´ os ´ grafj ´ an. ´ futtassuk le az eloz f (n) ˝ hogy N mindig megall.) ´ ´ merete: ´ (Felteheto, A graf c , ´ıgy ´ ´ ´ (A konfiguraci ´ os ´ adodik a log2 (cf (n) ) = O( (f (n))2 ) tarkorl at. ´ nem kesz´ ´ ıtjuk ˝ grafot ¨ el elore.)


83 / 184

´ ´ Az Immerman-Szelepcsenyi tetel ´ Tetel ´ ´ Letezik olyan nemdeterminisztikus lyukszalagos Turing-gep, ´ ´ ıtja adott G grafra ´ ´ annak x mely logaritmikus tarral kiszam´ es ˝ elerhet ´ ´ at. ´ ´ az x-bol o˝ csucsok ´ szam csucs ´ ara

´ Megjegyzes ´ akkor szam´ ´ ıt ki egy F(x) Egy nemdeterminisztikus gep ´ ´ ıtasi ´ sorozat fuggv ¨ enyt, ha minden x bemenetre minden szam´ ´ en ´ vagy h vagy ,,nem” allapotban ´ ´ meg (tehat ´ nem veg all ´ ´ ´ ıtasi ´ sorozatok), es ´ minden x bemenetre leteznek vegtelen szam´ ´ ´ ıtasi ´ sorozat, melynek veg ´ en ´ h allapotban ´ ´ letezik olyan szam´ all meg. Ebben az esetben az utolso´ szalag tartalma mindig F(x). ´ a munkaszavak hosszanak ´ ¨ Ha meg osszege mindig legfeljebb ´ ´ ıtja ki F(x)-et. ´ f (n) tarral szam´ f (|x|), akkor a gep


84 / 184

´ Bizony´ıtas ¨ n a csucsok ´ at ´ es ´ k = 0, 1, . . . , n − 1 eseten ´ legyen Jelolje ´ szam ˝ legfeljebb k hosszu´ uton ´ S(k) az x-bol ´ elerhet o˝ csucsok ´ ´ halmaza. Nekunk ¨ |S(n − 1)|-et kell meghataroznunk. ´ Vilagos, hogy S(0) = {x}, |S(0)| = 1. ´ ´ ahoz ´ ´ Az |S(k)| meghataroz as |S(k − 1)|-et hasznaljuk fel, ?

´ a´ egy olyan eljar ´ ast, ´ mely valaszt ´ tovabb ad az u ∈ S(k) ´ esre. ´ ´ ast: ´ kerd u = 1, 2, . . . , n-re megh´ıvjuk ezt az eljar 1. m := 0; válasz := nem; 2. Minden v = 1, 2, . . . , n csucsra ´ 2.1 ha v ∈ S(k − 1), akkor m := m + 1; ´ a´ (v, u) el ´ vagy v = u, akkor válasz := igen; 2.2 ha tovabb

´ ul 3. ha veg ¨ m < |S(k − 1)|, akkor ,,nem” ¨ ´ válasz ert ´ eke. ´ 4. kul ¨ onben az eredmeny


85 / 184

´ esre ´ Itt a v ∈ S(k − 1) kerd egy ,,pontatlan” nemdeterminisztikus ´ algoritmus ad valaszt, mely megsejt egy legfeljebb k hosszu´ ´ ellenorzi, ˝ ˝ v-be vezeto˝ ut-e. csucssorozatot ´ es hogy az egy x-bol ´ ´ eny: ´ ´ ´ as ´ ahoz ´ ´ Tarig aranyos az egy csucs ´ tarol szuks ¨ eges ´ sejtjuk terulettel: ¨ O(log n). (Az ut ´ egyes pontjait egyenkent ¨ meg.)

¨ ´ Kovetkezm eny ´ fuggv ´ Ha f (n) ≥ log n megengedett bonyolultsagi ¨ eny, akkor


NSPACE(f (n)) = coNSPACE(f (n)).

86 / 184

´ Bizony´ıtas ¨ egy f (n) tarkorl ´ ´ Tegyuk ¨ fel, hogy L-et eldonti atos ´ melyrol ˝ felteheto, ˝ hogy mindig nemdeterminisztikus Turing-gep, ´ ´ ´ ´ megall. Adott n hosszu´ bemeneten a konfiguraciok szama f (n) ´ ´ ≤ c , ´ıgy nemdeterminisztikus Turing-geppel O(f (n)) tarral ´ ´ ob ´ ol ´ elerhet ´ meghatarozhatjuk a kezdo˝ konfiguraci o˝ ´ ok ´ szam ´ at, ´ majd ennek alapjan ´ – az eloz ˝ o˝ konfiguraci ´ ´ – eldonthetj ¨ algoritmusban adott modszerhez hasonloan uk, ¨ ¨ ott ¨ van-e (,,igen”, ...) alaku. hogy ezek koz ´

´ Megjegyzes TIME(f (n)) = coTIME(f (n)) SPACE(f (n)) = coSPACE(f (n))


87 / 184

´ Visszavezetesek

´ olyan nehez, ´ mint A, ´ B problem ´ ak. ´ B legalabb Legyenek A es ´ ´ ´ ´ ha letezik olyan hatekony modszer, azaz f rekurz´ıv fuggv ¨ eny, ˝ ´ ´ mely az A tetszoleges x bemenetehez hozzarendeli a B egy ´ (peld ´ any ´ at) ´ ugy, ´ csak f (x) bemenetet ´ hogy az A-nak x akkor es ´ anya, ´ ´ anya. ´ akkor ,,igen” peld ha B-nek f (x) ,,igen” peld ´ ´ ´ Az f fuggv ¨ enyre tovabbi megszor´ıtasokat teszunk. ¨

Defin´ıcio´ ´ Azt mondjuk, hogy az L1 nyelv (logaritmikus tarral) ´ ´ visszavezetheto˝ az L2 nyelvre, ha letezik olyan O(log n) tarral ´ ıthato´ R szof ´ uggv ´ kiszam´ ¨ eny, hogy minden x bemenetre


x ∈ L1 ⇔ R(x) ∈ L2 .

88 / 184

´ ıtas ´ All´ ´ ´ ıtott Ha R egy M (lyukszalagos) Turing-geppel kiszam´ ´ akkor M minden x bemeneten polinom idoben ˝ visszavezetes, ´ megall.

´ Bizony´ıtas ´ ok ´ szama ´ Adott n hosszu´ x bemeneten a konfiguraci log n k ´ O(nc ) = O(n ). Ezek egyike sem fordulhat elo˝ ketszer egy ´ ıtasi ´ sorozatban. szam´ ´ minden logaritmikus tarral ´ ´ ıtott visszavezetes ´ Tehat kiszam´ ´ is. Tovabb ´ a´ |R(x)| az |x| egyben polinom ideju˝ visszavezetes ´ evel ´ ´ ´ polinom fuggv ¨ eny korlatozhat o.

´ Pelda ´ ÍTAS ´ visszavezetheto˝ MAXIMALIS ´ PAROS FOLYAM(E)-re.


89 / 184

´ HAMILTON-UT ◮ ◮

´ ıtott graf. ´ Adott: G irany´ ´ es: ´ letezik-e ´ Kerd olyan ut, ´ mely minden csucsot ´ pontosan ´ egyszer latogat meg?

SAT ◮ ◮

´ Adott: konjunkt´ıv normalalak u´ Boole-formula. ´ es: ´ kieleg´ ´ ıtheto-e? ˝ Kerd

´ ıtas ´ All´ ´ visszavezetheto˝ SAT-ra. HAMILTON-UT

´ Bizony´ıtas ´ ahoz ´ G csucsai: ´ 1, 2, . . . , n. A formula fel´ıras az xi,j , 1 ≤ i, j ≤ n ´ ´ ´ valtoz okat hasznaljuk. (Az xi,j igaz volta annak felel meg, hogy a j csucs ´ az i-edik egy Hamilton-uton.) ´ ´ ´ Bonyolultsagelm elet

90 / 184

´ ot ¨ reszformula ´ ´ ent ´ all´ ´ ıtjuk elo: ˝ A formulat konjunkciojak ^ ∀j∃i xi,j − (x1,j ∨ x2,j ∨ . . . ∨ xn,j ) j

∀j∀i1 < i2 (¬xi1 ,j ∨ ¬xi2 ,j ) −

^ ^

(¬xi1 ,j ∨ ¬xi2 ,j )

j i1
A ketto˝ egyutt: ¨ ∀j∃!ixi,j ∀i∃j xi,j −

^

(xi,1 ∨ xi,2 ∨ . . . ∨ xi,n )

i

∀i∀j1 < j2 (¬xi,j1 ∨ ¬xi,j2 ) −

^ ^

(¬xi,j1 ∨ ¬xi,j2 )

i j1 <j2

Egyutt: ¨ ∀i∃!jxi,j . ˝ fugg. Eddig csak n-tol ¨


91 / 184

´ nem kovetkezhet ¨ ∀(i, j) ∈ / E(G) az i csucs ´ utan j: ^

n−1 ^

(¬xk,i ∨ ¬xk+1,j )

k=1 (i,j)∈E(G) /

´ ´ ´ ıtheto, ˝ es ´ Adott G grafra a formula logaritmikus tarral elkesz´ ´ csak akkor van Hamilton-ut, G-ben akkor es ´ ha a formula ´ ıtheto. ˝ kieleg´


92 / 184

´ ozatok ´ Logikai hal Defin´ıcio´ ´ ozat: ´ ¨ ´ ıtott graf, ´ Hal kormentes irany´ ´ a csucsok ´ c´ımkezettek: ∧, ∨, ¬, igaz, hamis, xi ´ a csucs ∧, ∨ c´ımke eseten ´ befoka 2, ´ a csucs ¬ c´ımke eseten ´ befoka 1, ´ a csucs igaz, hamis, xi c´ımke eseten ´ befoka 0. ´ aban ´ ¨ ´ hogy pontosan egy csucs Altal megkovetelj uk ¨ meg, ´ kifoka legyen 0. ´ ´ koz ¨ ul Amennyiben a valtoz ok ¨ az x1 , . . . , xn fordulnak elo˝ a ´ ozatban ´ ´ ozat ´ ´ ıt egy hal (legfeljebb), akkor a hal kiszam´ n ´ {igaz, hamis} → {igaz, hamis} Boole-fuggv ¨ enyt.


93 / 184

´ ´ OZAT-KI ´ EKEL ´ ´ HAL ERT ES ◮ ◮

´ ´ ´ ozat. ´ Adott: valtoz omentes hal ´ es: ´ igaz-e az ert ´ eke? ´ Kerd

´ ˝ EG ´ OZAT-KIEL ´ ÍTHETOS ´ HAL EG ◮ ◮

´ ozat. ´ Adott: hal ´ es: ´ a valtoz ´ ´ ´ eket ´ Kerd oknak lehet-e ugy ´ ert adni, hogy a ´ ozat ´ ´ eke ´ igaz legyen? hal ert

´ ıtas ´ All´ ˝ EG ´ ´ visszavezetheto˝ a Az ELERHET OS ´ ´ ´ ´ ´ HALOZAT-KIERTEKEL ES-re.

´ ıtas ´ All´ ´ ˝ EG ´ OZAT-KIEL ´ ÍTHETOS ´ visszavezetheto˝ a SAT-ra. EG A HAL


94 / 184

´ ´ Minden g csucsnak ´ feleljen meg a g valtoz o. ´ x g c´ımkeje 7→ x ↔ g, azaz (¬x ∨ g) ∧ (x ∨ ¬g) ´ igaz g c´ımkeje 7→ g ´ hamis 7→ ¬g g c´ımkeje ´ ∨: g c´ımkeje g g ↔ (g1 ∨ g2 ), azaz րտ 7→ (¬g ∨ g1 ∨ g2 ) ∧ (¬g1 ∨ g) ∧ (¬g2 ∨ g) g1 g2 ´ ∧: g c´ımkeje g g ↔ (g1 ∧ g2 ), azaz րտ 7→ (¬g ∨ g1 ) ∧ (¬g ∨ g2 ) ∧ (¬g1 ∨ ¬g2 ∨ g) g1 g2 ´ ¬: g c´ımkeje g g ↔ (¬g1 ), azaz 7→ ↑ (¬g ∨ ¬g1 ) ∧ (g1 ∨ g) g1 g kimeno˝ kapu 7→ g


95 / 184

´ konjunkcioja. ´ A keresett formula: a fenti formulak ´ ozathoz ´ ´ ıtheto˝ logaritmikus tarral. ´ Adott hal a formula elkesz´ ´ a´ a hal ´ ozat ´ ´ csak akkor kieleg´ ´ ıtheto, ˝ ha a Tovabb akkor es formula az. ´ ıtheto, ˝ akkor tekintsunk Ha ugyanis a formula kieleg´ ¨ egy h ´ ıto˝ ert ´ ekel ´ es ´ et. ´ Ez minden egyes g kapuhoz es ´ xi kieleg´ ´ ´ ´ ´ eket. ´ valtoz ohoz meghataroz egy logikai ert Rendeljuk ¨ minden ´ ´ ´ eke ´ a kapuhoz ezt a logikai erteket. Ekkor a kimeneti kapu ert ´ ozat ´ ´ eke, ´ ´ ´ ek ´ et ´ h(xi )-nek hal ert amikor minden xi valtoz o´ ert ´ valasztjuk. ´ ozat ´ ´ ıtheto, ˝ akkor valasszuk ´ Ha a hal kieleg´ meg minden xi ´ ek ´ et ´ ugy, ´ ozat ´ ´ eke ´ igaz legyen. Szam´ ´ ıtsuk ki a ert ´ hogy a hal ert ´ ozat ´ ´ ´ ek ´ et. ´ Az ´ıgy kapott ert ´ ekel ´ es ´ hal minden kapujanak ert ´ ıti a formulat. ´ kielelet eg´ ´ ´ Bonyolultsagelm

96 / 184

´ ´ ıti a Hg valtoz ´ ´ Az egyik irany: ha Hg -t kieleg´ oinak egy h ´ ekel ´ ese, ´ ´ kiert akkor h-nak az a folytatasa, mely Hg minden g′ ´ ek ´ et ´ rendeli a h ert ´ ekel ´ es ´ ´ ´ ´ csucs ´ ahoz (mint valtoz ohoz) a Hg′ ert ´ ıti Fg -t. mellett, kieleg´ ´ ´ ´ ıti egy h ert ´ ekel ´ es ´ (mely ert ´ eket ´ A masik irany: ha Fg -t kieleg´ ad ´ ´ ´ minden csucs ´ ´ Hg Hg valtoz oinak es ´ anak), akkor h megszor´ıtasa ´ ´ ´ ıti a Hg hal ´ ozatot. ´ valtoz oira kieleg´


97 / 184

´ tranzitivitasa ´ A visszavezetes

´ ´ reflex´ıv. Vilagos, hogy a visszavezetes

´ Tetel ´ tranzit´ıv: Ha R az L1 -nek L2 -re, R′ pedig az A visszavezetes ¨ ´ L2 -nek L3 -ra valo´ visszavezetese, akkor az R ◦ R′ osszetett ´ L1 -nek L3 -ra valo´ visszavezetese. ´ fuggv ¨ eny

´ Bizony´ıtas ´ ´ ıto´ ´ MR′ az R-et ill. R′ -t logaritmikus tarral Legyen MR es kiszam´ ´ ´ ıtunk lyukszalagos Turing-gepek. Elkesz´ ¨ egy olyan lyukszalagos ´ ´ ´ ıtja R ◦ R′ -t. (Ez Turing-gepet, mely logaritmikus tarral kiszam´ ´ ´ mert R(x) sokkal nem lehet a hagyomanyos szuperpoz´ıcio, hosszabb lehet, mint log |x|.)


98 / 184

´ tranzitivitasa ´ A visszavezetes A trukk ¨ ´ at ´ ´ ´ csak a mutato´ poz´ıcioj Nem taroljuk el MR kimeno˝ szalagjat, (kezdetben ez 1). x MR i MR ′

(R ◦ R′ )(x) ´ ¨ ¨ ege van a kovetkez o˝ karakterre: folytatjuk MR MR′ -nek szuks ´ as ´ at. ´ szimulal ´ ˝ o˝ karakterre: elolr ¨ ol ˝ kezdjuk ¨ ege van az eloz MR′ -nek szuks ¨ MR ´ as ´ at. ´ szimulal


99 / 184

Defin´ıcio´ ´ osztaly ´ zart ´ a Azt mondjuk, hogy egy C bonyolultsagi ´ ´ ´ ha valahanyszor L visszavezetheto˝ L′ -re es visszavezetesre, ′ L ∈ C, mindig teljesul, ¨ hogy L ∈ C.

´ ıtas ´ All´ ´ ´ Az L, NL, P, NP, PSPACE, EXP osztalyok zartak a ´ visszavezetesre.

´ Bizony´ıtas ´ NL eseten ´ az eloz ˝ o˝ tetelhez ´ ´ hasonloan. ´ L es (tranzitivitas) A ¨ ´ eseteben ´ ´ tobbi osztaly a hagyomanyos szuperpoz´ıcio´ is megfelel.

´ Megjegyzes ´ ´ nemtrivialis ´ L, L′ elemere ´ igaz, hogy L L barmely ket ′ visszavezetheto˝ L -re. ´ ´ Bonyolultsagelm elet

100 / 184

Defin´ıcio´ ´ ´ osztaly. ´ Egy L nyelvet C-neheznek Legyen C egy bonyolultsagi nevezunk, ¨ ha minden L′ ∈ C nyelv visszavezetheto˝ L-re. Ha ´ L ∈ C is teljesul, meg ¨ akkor L C-teljes. ´ ´ ak. ´ Specialisan: P-teljes, NP-teljes stb. problem

´ ıtas ´ All´ ´ a visszavezetesre ´ ´ az L nyelv C-teljes. Tegyuk ¨ fel, hogy C zart es ˝ all, ´ melyek Akkor C pontosan azon L′ nyelvekbol ´ az egesz ´ osztalyt! ´ ˝ L-re. Tehat ´ L reprezentalja visszavezethetok

´ ıtas ´ All´ ´ L Tegyuk ¨ fel, hogy L egy C-teljes nyelv, L′ ∈ C es visszavezetheto˝ L′ -re. Akkor L′ is C-teljes.

´ ıtas ´ All´ L nyelv C-teljes ⇔ L coC-teljes.


101 / 184

´ Egy P-teljes problema ´ Tetel ´ ´ OZAT-KI ´ EKEL ´ ´ problema ´ A HAL ERT ES P-teljes.

´ Bizony´ıtas ´ ´ E celb ´ ol ´ Csak azt mutatjuk meg, hogy a problema P-nehez. ´ legyen L ∈ P, be kell latnunk, hogy L visszavezetheto˝ a ´ ´ OZAT-KI ´ EKEL ´ ´ problem ´ ara. ´ HAL ERT ES ´ ˝ ´ Mivel L ∈ P, letezik olyan polinom idokorl atos egyszavas M ´ mely eldonti ¨ L-et. Tegyuk Turing-gep, ¨ fel, hogy p(n) − 2 az M ˝ ´ polinom idokorl atja, ahol p(n) > 2. ´ ˝ hogy M Ha megengedunk ¨ ures ¨ atmeneteket is, ugy ´ felteheto, ´ esben ´ ´ minden n hosszu´ x bemeneten pontosan p(n) − 2 lep all ´ meg ,,igen” vagy ,,nem” allapotban.


102 / 184

´ Egy P-teljes problema

´ askor ´ Azt is feltehetjuk, ¨ hogy M a megall a mutato´ a ⊲ ´ ¨ o˝ karakteren all, ´ es ´ ez a karakter az ,,igen” szimbolumot kovet ´ vagy a ,,nem” allapot. ¨ es ´ et ´ az n hosszu´ x bemeneten le´ırhatjuk egy M muk ˝ od ´ u˝ T = (Ti,j ) tabl ´ azattal, ´ (p(n) − 1) × p(n) meret Ti,j ∈ Γ = Σ ∪ {σq : σ ∈ Σ, q ∈ K}. ´ ´ q allapotban ´ Itt σq jelentese: a gep van, a mutato´ az adott ¨ ki, mely σ. karaktert jeloli ´ kedve´ ert ´ most feltesszuk, ´ Az egyszerus ˝ eg ¨ hogy indulaskor a ´ a ⊲ szimbolumot ´ ¨ o˝ karakterre mutat, es ´ a⊲ gep kovet ´ ´ szimbolumra sosem kerul ¨ a mutato.


103 / 184


⊲ ⊲ ⊲ ⊲ ⊲ ⊲ ⊲ ⊲ ⊲

x

↑ ,,igen” v. ,,nem”


⊔ ⊔ ...⊔ ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ ⊔

104 / 184

´ Egy P-teljes problema ´ o˝ elemek adottak. Minden belso˝ elem a fol ¨ otte ¨ A szels levo˝ ´ ´ ˝ fugg harom fuggv ¨ enye valamely M-tol ¨ o˝ f : Γ3 → Γ ´ szerint. fuggv ¨ eny ´ Amennyiben Γ elemeit bitsorozatokkal kodoljuk, f helyettes´ıtheto˝ fℓ : {igaz, hamis}3m → {igaz, hamis} ´ (ℓ = 1, 2, . . . , m, m = ⌈log |Γ|⌉) fuggv ¨ enyekkel. ´ ozatot ´ Az x bemenethez tartozo´ R(x) hal ugy ´ kapjuk, hogy a ´ azat ´ ´ at ´ helyettes´ıtjuk tabl minden belso˝ poz´ıcioj ¨ egy egyszeru˝ ´ ozattal ´ ´ ˝ fuggetlen hal (melyek veges sok, x-tol ¨ ul ¨ megadhato´ ´ ´ ´ halozatt´ıpusbol kerulnek ¨ ki).


105 / 184


´ o˝ elem: a megfelelo˝ elem binaris ´ kodj ´ ahoz ´ ´ csak szels tartozo, ˝ ucsokat ´ ozat. ´ kezdocs ´ tartalmazo´ hal ´ m kimenettel rendelkezo, ˝ az belso˝ elem: 3m bemenettel es ´ ´ ıto´ hal ´ ozat. ´ f1 , . . . , fm fuggv ¨ enyeket kiszam´ ´ kerul ´ ozatok ´ A belso˝ elemek helyere ¨ o˝ hal bemeneteit rendre ¨ otte ¨ ´ ´ ozat ´ azonos´ıtjuk a fol levo˝ harom hal kimeneteivel. ´ hal ´ ozat ´ ´ ´ ozat ´ anak ´ Az egesz kimenete: az utolso´ sor masodik hal elso˝ kimenete. ´ Vilagos, hogy ◮ R(x) elkesz´ ´ ıtheto˝ logaritmikus tarig ´ eny ´ u˝ Turing-geppel; ´ ◮

´ eke ´ igaz. x ∈ L ⇔ R(x) ert


106 / 184

´ Cook tetele

´ Tetel ´ A SAT problema NP-teljes. ´ ´ hogy SAT ∈ NP. Mivel a Az nyilvanval o, ´ ˝ EG ´ ´ ÍTHETOS ´ visszavezetheto˝ SAT-ra, ´ıgy HALOZAT-KIELEG ´ ˝ EG ´ ´ ÍTHETOS ´ ´ elegendo˝ belatni, hogy a HALOZAT-KIEL EG ´ (Persze akkor NP-teljes is.) NP-nehez.


107 / 184

´ Cook tetele

´ Tetel’ ´ ˝ EG ´ OZAT-KIEL ´ ÍTHETOS ´ NP-teljes. A HAL EG

´ Bizony´ıtas ´ Legyen L egy M nemdeterminisztikus egyszavas Turing-geppel ´ ´ ´ ´ ´ ˝ ¨ ott ¨ nyelv. A HALOZAT-KIERTEKELES polinom idoben eldont ´ enek ´ ´ at ´ kovetve, ¨ P-teljesseg bizony´ıtas adott x bemenethez ´ ıtunk ´ azatot, ´ elkesz´ ¨ egy T tabl mely a nemdeterminisztikus ´ ´ ´ is fugg. ˝ hogy minden konfiguraci ´ oban ´ valaszt asokt ol ¨ Felteheto, ´ ´ lehetseges, ´ 2 valaszt as ´ıgy c egy t = p(|x|) hosszu´ bitsorozat, ˝ ´ at ´ megado´ polinom fuggv ´ ahol p az M idokorl atj ¨ eny.


108 / 184

´ Cook tetele

´ eke ´ most a Ti−1,j−1 , Ti−1,j , Ti−1,j+1 A belso˝ Ti,j elemek ert ´ ekeken ´ ˝ is fugg, ert k´ıvul ¨ a ci -tol ¨ ami 0 vagy 1. Így az fℓ fuggv ´ ¨ enyek: {igaz, hamis}3m+1 → {igaz, hamis}. ´ ozatot ´ ´ ´ kesz´ ´ ıtjuk Az R(x) hal a korabbiakhoz hasonloan ¨ el azzal ¨ ´ ´ ozat ´ ´ c1 , . . . , ct a kul ¨ onbs eggel, hogy a hal rendelkezik meg ´ ´ ´ bemeneti kapukkal, amelyek x1 , . . . , xt valtoz okkal c´ımkezettek.


109 / 184

´ egy jellemzese ´ Az NP osztaly Defin´ıcio´ ˝ Legyen R ⊆ Σ∗ × Σ∗ . Azt mondjuk, hogy R polinom idoben ¨ ˝ ha az eldonthet o, LR = {x; y : R(x, y)} nyelv az. ´ Azt mondjuk, hogy R polinomialisan kiegyensulyozott, ´ ha van olyan p(n) polinom, hogy R(x, y) ⇒ |y| ≤ p(|x|).

´ ıtas ´ All´ ˝ ¨ ˝ polinomialisan ´ L ∈ NP ⇔ ∃R polinom idoben eldonthet o, ´ o, ´ hogy kiegyensulyozott ´ relaci


L = {x : ∃y R(x, y)}.

110 / 184

´ Bizony´ıtas ´ ¨ o, ˝ p(n) polinom ⇒ Tegyuk ¨ fel, hogy L ∈ NP. Letezik L-et eldont ˝ ´ ´ idokorlatos nemdeterminisztikus Turing-gep. Legyen R = {(x, y) : y az x-hez tartozo´ elfogado´ ´ ıtasi ´ sorozatot kodol}. ´ szam´ ˝ ⇐ Legyen L = {x : ∃y R(x, y)}, ahol R polinom idoben ¨ ´ polinomialisan ´ eldonthet o˝ es kiegyensulyozott: ´ R(x, y) ⇒ |y| ≤ p(|x|). ´ adott x eseten ´ Az N nemdeterminisztikus Turing-gep ´ ˝ ´ nemdeterminisztikusan generaljon egy tetszoleges y szot, ˝ ¨ o˝ amire |y| ≤ p(|x|), majd az LR -et polinom idoben eldont ´ ´ ˝ Turing-gepet szimulalva ellenorizze, hogy R(x, y) teljesul-e. ¨


111 / 184

´ ıthetos ˝ eg ´ valtozatai ´ A kieleg´

Defin´ıcio´ ´ esete, amelyben Legyen k ≥ 1. A kSAT a SAT azon specialis ´ ¨ oz ¨ o) ˝ literalb ´ ol ´ all. ´ minden tag pontosan k (nem feltetlen ul ¨ kul ¨ onb


112 / 184

3SAT ´ ıtas ´ All´ ´ ´ıgy k ≥ 3 eseten ´ kSAT NP-teljes. 3SAT NP-teljes, es

´ Bizony´ıtas ℓ 7→ ℓ ∨ ℓ ∨ ℓ ℓ1 ∨ ℓ2 7→ ℓ1 ∨ ℓ2 ∨ ℓ2 ℓ1 ∨ ℓ2 ∨ ℓ3 7→ ℓ1 ∨ ℓ2 ∨ ℓ3 ℓ1 ∨ ℓ2 ∨ ℓ3 ∨ ℓ4 7→ .. .

(ℓ1 ∨ ℓ2 ∨ x) ∧ (¬x ∨ ℓ3 ∨ ℓ4 ) .. .

ℓ1 ∨ ℓ2 ∨ . . . ∨ ℓn 7→ (ℓ1 ∨ ℓ2 ∨ x) ∧ (¬x ∨ ℓ3 ∨ y) ∧


(¬y ∨ ℓ4 ∨ z) ∧ . . . ∧ (¬u ∨ ℓn−1 ∨ ℓn )

113 / 184

3SAT

´ ıtas ´ All´ ´ ´ u´ Legyen ϕ = c1 ∧ c2 ∧ . . . . . . ∧ ck konjunkt´ıv normalform aj ′ ˝ oekben ˝ formula. Minden ci taghoz legyen ci az eloz adott ´ ahol minden kifejezesben ´ ´ ´ ´ kifejezes, uj ´ valtoz okat hasznalunk. ´ csak akkor kieleg´ ´ ıtheto, ˝ ha Ekkor ϕ akkor es ϕ′ = c′1 ∧ c′2 ∧ . . . ∧ c′k az. ´ 3SAT ∈ NP, ezert ´ SAT Mivel SAT visszavezetheto˝ 3SAT-ra es ´ eb ´ ol ˝ kovetkezik, ¨ NP-teljesseg hogy 3SAT is NP-teljes.


114 / 184

2SAT ´ ol ´ all. ´ Legyen ϕ olyan k.n.f., hogy ϕ minden tagja 2 literalb

G(ϕ) ◮ ◮

˝ ´ ´ es ´ negaltjaik. ´ csucsok: ´ a ϕ-ben elofordul o´ valtoz ok ´ ´ ⇔ α ∨ β vagy β ∨ α a ϕ tagja (azaz ha elek: (α, β) el α → β vagy β → α a ϕ tagja.)

´ ıtas ´ All´ ´ csak akkor vezet α-bol ´ β-ba irany´ ´ ıtott ut, ´ Akkor es ´ ha letezik ´ α-ba vezeto˝ irany´ ´ ıtott ut. β-bol ´

´ Tetel ´ csak akkor kieleg´ ´ ıtheto, ˝ ha nincs olyan x A ϕ formula akkor es ´ ´ amelyre letezik ´ ´ ıtott ut ˝ ¬x-be es ´ valtoz o, G(ϕ)-ben irany´ ´ x-bol vissza. ´ ´ Bonyolultsagelm elet

115 / 184

2SAT ´ Bizony´ıtas ´ ´ ´ hogy x-bol ˝ elerhet ´ Tegyuk ¨ fel, hogy letezik olyan x valtoz o, o˝ ¬x, ´ ¬x-bol ˝ elerhet ´ es o˝ x. ´ ´ ´ tetszoleges ˝ ´ ekel ´ es ´ ere ´ ϕ hamis. Belatjuk, hogy a valtoz ok T kiert ´ Tegyuk ¨ fel, hogy T(x) igaz (a T(x) hamis eset hasonloan ˝ Mivel T(¬x) hamis, az x-bol ˝ ¬x-be vezeto˝ uton kezelheto). ´ ´ ´ ´ letezik olyan (α, β) el, hogy T(α) igaz es T(β) hamis. Ekkor ´ szerint a megfelelo˝ tag (α ∨ β vagy β ∨ α) G(ϕ) konstrukcioja hamis, ´ıgy ϕ hamis. ´ ´ sem letezik ´ ˝ ¬x-be es ´ Tegyuk ¨ fel, hogy egyetlen x valtoz ora x-bol ˝ x-be vezeto˝ ut. ´ ıtjuk ´ ´ egy olyan T ¬x-bol ´ Elkesz´ ¨ a valtoz ok ´ ekel ´ es ´ et, ´ melyre ϕ igaz. kiert


116 / 184

2SAT

´ ´ ´ amelynek igazsag ´ ert ´ ek ´ et ´ meg ´ Valasszunk egy olyan x valtoz ot, ¨ ıtettuk. ˝ nem erhet ´ nem rogz´ ¨ Ha x-bol o˝ el ¬x, akkor legyen ¨ ˝ nem erhet ´ α := x, kul ¨ onben (ekkor ¬x-bol o˝ el x) α := ¬x. ´ minden α-bol ´ elerhet ´ α-hoz es o˝ csucshoz ´ rendeljuk ¨ az igaz ´ eket ´ ´ tagadasaikhoz ´ ´ eket. ´ ert es rendeljuk ¨ a hamis ert ˝ elerhet ´ (Ezek pontosan azok, melyekbol o˝ α.) ´ α ´ definialt, ´ nem lehet: α β es β, mert ekkor β α T jol ´ β es α miatt α α lenne. ´ ´ eket ´ ´ nem lehet, hogy β korabban hamis ert α β eseten ´ α mar ´ korabban ´ kapjon, mert akkor β α alapjan hamis ´ eket ´ ert kapott volna. ´ ´ es ´ T(α) igaz, T(β) is igaz. Ezert ´ ϕaT Valahanyszor (α, β) el ´ ekel ´ es ´ mellett igaz. kiert


117 / 184

2SAT

¨ ´ Kovetkezm eny 2SAT ∈ NL, ´ıgy 2SAT ∈ P.

´ Bizony´ıtas ´ Mivel NL = coNL, elegendo˝ azt belatni, hogy 2SAT − KOMPLEMENTER ∈ NL. ¨ ´ hogy letezik-e ´ Ehhez azt kell eldonteni adott ϕ eseten, ´ ´ x-bol ˝ ¬x-be es ´ vissza vezeto˝ ut. G(ϕ)-ben valamely x valtoz ora ´ ¨ Ez ugyanugy ´ eldonthet o˝ nemdeterminisztikusan logaritmikus ˝ EG. ´ ´ ´ tarral, mint az ELERHET OS


118 / 184

´ ´ ´ ak ´ NP-teljes grafelm eleti problem ¨ ´ FUGGETLEN CSUCSHALMAZ ´ ıtatlan graf, ´ K szam. ´ Adott: G = (V, E) irany´ ´ es: ´ Letezik-e ´ Kerd K elemu˝ fuggetlen ¨ csucshalmaz? ´

´ Tetel ¨ ´ ´ A FUGGETLEN CSUCSHALMAZ problema NP-teljes.

´ Bizony´ıtas ´ ´ Vilagos, hogy a problema NP-ben van. Megmutatjuk, hogy ¨ ´ 3SAT visszavezetheto˝ a FUGGETLEN CSUCSHALMAZ-ra. ´ anya, ´ ´ Legyen ϕ a 3SAT egy peld ϕ = c1 ∧ . . . ∧ cm . A G graf ´ ¨ ol, ˝ melyek a ci tagoknak felelnek ´ ogb alljon m darab haromsz ´ o˝ literaloknak ´ meg, s melyek csucsai ´ a ci -kben lev felelnek meg. ´ ´ ´ koss ¨ unk ¨ ´ minden ellentetes literalt. Ezen k´ıvul ¨ meg ¨ ossze ellel ´ Vegul ¨ legyen K = m. ´ ıtheto˝ ⇔ G-ben letezik ´ ϕ kieleg´ K elemu˝ fuggetlen ¨ csucshalmaz. ´


119 / 184

´ ´ ´ ak ´ NP-teljes grafelm eleti problem KLIKK ´ ıtatlan graf, ´ K szam. ´ Adott: G = (V, E) irany´ ´ es: ´ Letezik-e ´ ´ ´ Kerd K elemu˝ klikk (teljes reszgr af)?

´ Tetel KLIKK NP-teljes.

´ Bizony´ıtas ´ Vilagos, hogy KLIKK ∈ NP. ¨ ´ Legyen (G = (V, E), K) a FUGGETLEN CSUCSHALMAZ ´ ´ anya. ´ ˝ hogy K ≤ |V|. problema egy peld Felteheto, ´ ´ Vilagos, hogy Legyen Gc = (V, Ec ) a G komplementer grafja. ´ csak akkor letezik ´ G-ben akkor es K elemu˝ fuggetlen ¨ ´ csucshalmaz, ´ ha Gc -ben letezik K elemu˝ klikk.


120 / 184

´ ´ ´ ak ´ NP-teljes grafelm eleti problem ´ ´ CSUCSLEFED ES ´ ıtatlan graf, ´ K szam. ´ Adott: G = (V, E) irany´ ´ es: ´ Letezik-e ´ Kerd olyan K elemu˝ csucshalmaz, ´ hogy ´ illeszkedik a halmaz egy csucs ´ minden el ´ ahoz?

´ Tetel ´ ´ problema ´ A CSUCSLEFED ES NP-teljes.

´ Bizony´ıtas ¨ ´ Legyen (G = (V, E), K) a FUGGETLEN CSUCSHALMAZ ´ ´ anya, ´ problema egy peld ahol K ≤ |V|. ´ csak akkor letezik ´ G-nek akkor es K elemu˝ fuggetlen ¨ ´ lefedhetoek ˝ |V| − K elemu˝ csucshalmaza, ´ ha elei csucshalmazzal. ´


121 / 184

´ HAMILTON-UT ´ ıtatlan graf. ´ Adott: G = (V, E) irany´ ´ es: ´ Letezik-e ´ Kerd olyan ut, ´ melyben minden csucs ´ ˝ pontosan egyszer fordul elo?

´ Tetel ´ problema ´ A HAMILTON-UT NP-teljes.

´ Tetel ´ A TSP(E) problema NP-teljes.

´ Bizony´ıtas ´ problem ´ at ´ visszavezetjuk A HAMILTON-UT ¨ a TSP(E) ´ ara. ´ problem ´ az {1, . . . , n} halmazon. Ha i 6= j es ´ Legyen G egy n csucs ´ u´ graf ´ akkor di,j legyen 1, kul ¨ (i, j) el, ¨ onben legyen di,j = 2. G-ben ´ csak akkor letezik ´ ´ akkor es Hamilton-ut, ´ ha letezik ≤n+1 ¨ ¨ eg ´ u˝ kor ¨ ut. osszk olts ´


122 / 184

´ ´ ´ ak ´ NP-teljes grafelm eleti problem ´ 3-SZÍNEZES ´ ıtatlan graf. ´ Adott: G = (V, E) irany´ ´ es: ´ Kisz´ınezhetoek-e ˝ ´ csucsai Kerd a graf ´ 3 sz´ınnel ugy, ´ ´ ¨ oz ¨ o˝ sz´ınuek hogy a szomszedos csucsok ´ kul ¨ onb ˝ legyenek?

´ Tetel ´ problema ´ A 3-SZÍNEZES NP-teljes.

´ Megjegyzes ´ problema ´ A 2-SZÍNEZES P-ben van. ´ ´ ´ s´ıkbarajzolhato´ grafokra. ´ ´ trivialis A 4-SZINEZES problema


123 / 184

´ ak ´ halmazokra es ´ szamokra ´ NP-teljes problem ´ ÍTAS ´ HARMAS ´ ´ u˝ halmaz, F (fiuk), ´ Adott: Harom azonos meret ´ L (lanyok), ´ ´ ´ ´ H (hazak), es egy R ⊆ F × L × H relacio. ´ es: ´ Megadhato-e ´ az R-beli harmasok ´ Kerd egy olyan ´ ´ es ´ haz ´ pontosan reszhalmaza, melyben minden fiu, ´ lany egyszer szerepel?

´ ÍTAS ´ ∈ NP. ´ Vilagos, hogy HARMAS

´ Tetel ´ ÍTAS ´ problema ´ A HARMAS NP-teljes.

´ Megjegyzes ´ ÍTAS ´ ∈ P. PAROS


124 / 184

´ Bizony´ıtas ´ ÍTAS-ra. ´ A 3SAT-ot vezetjuk ¨ vissza HARMAS ϕ = c1 ∧ . . . ∧ cm ´ ´ jelolje ¨ k az x es ´ ¬x elofordul ˝ ´ Adott x valtoz ora asainak ´ Az x valtoz ´ ´ ´ ´ an ´ maximumat. ohoz felveszunk ¨ 2k harmast, az abr ´ ´ ¨ lathat o´ haromsz ogeket: h1


ℓk

h2

f1 ℓ1

h3 f2 ℓ2

h4 125 / 184

´ ÍTAS ´ HARMAS ´ folytatasa ´ Bizony´ıtas ˝ ´ ahoz ´ ´ Az x minden egyes elofordul as hozzarendel unk ¨ egy ´ ˝ ´ ahoz ´ as pedig egy paratlan indexu˝ hi -t, a ¬x minden elofordul ´ paros indexu˝ hi -t. ´ an ´ szereplo˝ fiuk ´ lanyok ´ ´ harmasokban ´ Mivel az abr ´ es mas nem ´ ´ ´ szerepelnek, minden harmas´ıtasban minden masodik ´ ¨ szerepel: haromsz og (f1 , ℓ1 , h2 ), (f2 , ℓ2 , h4 ), . . . x igaz (f1 , ℓk , h1 ), (f2 , ℓ1 , h3 ), . . . x hamis ´ 3 harmast, ´ Minden cj taghoz felveszunk ¨ meg melyek (f , ℓ, h) ˝ fuggnek, ´ ´ alakuak, ´ ahol f , ℓ csak a cj -tol ¨ h pedig azon harom haz ´ valamelyike, melyek a tagban szereplo˝ literaloknak felelnek meg. ´ ıtett R relaci ´ ora ´ erv ´ enyes: ´ Az eddig elkesz´ ´ csak akkor adhato´ meg az R egy olyan reszhalmaza, ´ Akkor es ´ lany ´ pontosan egyszer, es ´ minden haz ´ melyben minden fiu´ es ´ ıtheto. ˝ legfeljebb egyszer szerepel, ha ϕ kieleg´ ´ ´ Bonyolultsagelm elet

126 / 184

´ ÍTAS ´ HARMAS

´ A konstrukcio´ befejezese ´ ugyanannyi lanyt ´ ´ ´ H2 + m ≤ H2 + H3 fiut ´ es Eddig H ≥ 3m hazat es ´ hasznaltunk. ¨ ´ ´ K lanyt ´ ¨ K a H − ( H2 + m) kul ¨ onbs eget. Felveszunk ¨ meg Jelolje ´ fiut, ´ ´ es ´ melyek mindegyik hazba belerakhatok.


127 / 184

´ HALMAZLEFEDES ´ Adott: Egy U halmaz reszhalmazainak C = (S1 , . . . , Sn ) ´ ´ rendszere es egy K szam. ´ es: ´ Kivalaszthat ´ ´ K darab az Si -k koz ¨ ul Kerd o-e ¨ ugy, ´ hogy ´ U? ezek egyes´ıtese

´ HALMAZPAKOLAS ´ Adott: Egy U halmaz reszhalmazainak C = (S1 , . . . , Sn ) ´ egy K szam. ´ rendszere es ´ es: ´ Kivalaszthat ´ ´ az Si -k koz ¨ ul ´ ´ Kerd o-e ¨ K paronk ent diszjunkt halmaz?

´ HARMASOKKAL ´ PONTOS LEFEDES ´ 3-elemu˝ Adott: Egy 3m elemu˝ U halmaz es ´ reszhalmazainak (S1 , . . . , Sn ) rendszere. ´ es: ´ Kivalaszthat ´ ´ m darab Si ugy, Kerd o-e ´ hogy ezek ´ U? (A kivalasztott ´ ´ diszjunktak.) egyes´ıtese Si -k nyilvan


128 / 184

´ ak ´ halmazokra NP-teljes problem

´ Tetel ´ HALMAZPAKOLAS, ´ PONTOS LEFEDES ´ A HALMAZLEFEDES, ´ ´ ak ´ NP-teljesek. HARMASOKKAL problem

´ Bizony´ıtas ´ ÍTAS ´ a PONTOS LEFEDES ´ HARMASOKKAL ´ A HARMAS ´ esete. specialis ´ HARMASOKKAL ´ ´ A PONTOS LEFEDES a HALMAZLEFEDES, ´ ´ esete is. valamint a HALMAZPAKOLAS specialis


129 / 184

´ ´ EK ´ U ˝ PROGRAMOZAS ´ EGESZ ERT ´ ´ egesz ´ egyutthat ´ linearis ´ Adott: Egy n-valtoz os, ¨ os ˝ ´ egyenlotlens eg-rendszer. ´ es: ´ Letezik-e ´ ´ ert ´ ek ´ u˝ megoldas? ´ Kerd egesz

´ felfoghato´ az EGESZ ´ ´ EK ´ U ˝ A HALMAZLEFEDES ERT ´ specialis ´ esetekent: ´ PROGRAMOZAS n X xi ≤ B, 0 ≤ xi ≤ 1, Ax ≥ 1, i=1

ahol A oszlopai a halmazrendszer elemeinek felelnek meg. ´ ´ EK ´ U ˝ Azt is meg lehet mutatni, hogy az EGESZ ERT ´ NP-ben van. PROGRAMOZAS

´ Tetel ´ ´ EK ´ U ˝ PROGRAMOZAS ´ problema ´ Az EGESZ ERT NP-teljes.


130 / 184

´ ak ´ halmazokra es ´ szamokra ´ NP-teljes problem

´ ´ EK ´ U ˝ PROGRAMOZAS ´ egy masik ´ ´ Az EGESZ ERT specialis esete:

´ ´ HATIZS AK ´ ´ ci ert ´ eke, ´ Adott: n elem mindegyikenek wi sulya ´ es ´ valamint W es K. ´ es: ´ Kivalaszthat ´ ´ ismetl ´ es ´ nelk ´ ul ´ any ´ elem ugy, Kerd o-e ¨ neh ´ ¨ ´ ek ´ uk ´ osszs ¨ hogy ossz ert ¨ ≥ K es ulyuk ´ ≤ W?

´ Tetel ´ ´ problema ´ A HATIZS AK NP-teljes.


131 / 184

´ A coNP osztaly Defin´ıcio´ coNP = {L : L ∈ NP}

´ ak ´ Peld ´ ENYESS ´ ´ ERV EG Adott: ϕ Boole-formula ´ enyes-e, ´ es: ´ Erv ´ Kerd azaz azonosan igaz-e ϕ? ´ HAMILTON-UT KOMPLEMENTER ´ Adott: G graf ´ es: ´ Igaz-e, hogy G nem tartalmaz Hamilton-utat? Kerd

´ ıtas ´ All´ ´ ENYESS ´ ´ es ´ KOMPLEMENTER ´ HAMILTON-UT Az ERV EG ´ ak ´ coNP-ben vannak. problem


132 / 184

´ coNP NP es

´ Egy problema akkor van ◮

´ any ´ ahoz ´ ´ ¨ or, ¨ NP-ben, ha minden igen peld letezik tom ˝ ˝ ´ es ´ csak az igen polinom idoben ellenorizhet o˝ bizony´ıtek, ´ anyokhoz ´ ´ ´ peld letezik ilyen bizony´ıtek.

◮

´ anyhoz ´ ´ ¨ or, ¨ coNP-ben, ha minden nem peld letezik tom ˝ ˝ ´ ´ csak a nem polinom idoben ellenorizhet o˝ cafolat, es ´ anyokhoz ´ ´ ´ peld letezik ilyen cafolat.

´ ıtas ´ All´ ´ ENYESS ´ ´ es ´ KOMPLEMENTER ´ HAMILTON-UT Az ERV EG ´ ak ´ coNP-teljesek. problem


133 / 184

´ coNP NP es ´ ıtas ´ All´ P ⊆ NP ∩ coNP.

´ ıtas ´ All´ ´ a visszavezetesre ´ ´ L C-teljes. Tegyuk ¨ fel, hogy C zart es Ekkor C = coC ⇔ L ∈ coC.

¨ ´ Kovetkezm eny ´ ENYESS ´ ´ ∈ NP. NP = coNP ⇔ SAT ∈ coNP ⇔ ERV EG


134 / 184

PRÍMEK ´ (binarisan). ´ Adott: p szam ´ es: ´ Pr´ımszam-e ´ Kerd p?

´ ıtas ´ All´ PRÍMEK ∈ coNP.

´ (Lucas) Tetel ´ akkor es ´ csak akkor pr´ımszam, ´ ´ Egy p > 1 szam ha letezik olyan 1 ≤ r < p, amelyre: (a) rp−1 ≡ 1 mod p ´ osztoj ´ ara ´ r(p−1)/q 6≡ 1 mod p. (b) A p − 1 minden q pr´ımszam

´ Pelda p = 5 → r = 3: 34 ≡ 1 mod 5, 32 ≡ 4 mod 5.


135 / 184

´ Pratt tetele

´ (Pratt, 1975) Tetel PRÍMEK ∈ NP ∩ coNP.

´ Bizony´ıtas ˝ hogy p > 2. Legyen adott p. Felteheto, ´ voltanak ´ ´ A p pr´ımszam bizony´ıteka: (r, q1 , . . . , qk ), ´ a´ q1 , . . . , qk a p − 1 osszes ¨ ahol 1 ≤ r < p, rp−1 ≡ 1 mod p, tovabb ´ es ´ ´ıgy k ≤ ⌈log p⌉ es ´ r(p−1)/qi 6≡ 1 mod p, i = 1, . . . , k. pr´ımosztoi,


136 / 184

´ Pratt tetele

´ Az input merete n = ⌈log p⌉.

´ ıtas ´ All´ ´ ˝ rp−1 mod p meghatarozhat o´ valamely m-re O(nm ) idoben.

´ Bizony´ıtas n

´ ´ majd Kepezz uk ¨ az r mod p, r2 mod p, . . . , r2 mod p szamokat, i 2 ´ ¨ ul ¨ ezek koz ¨ osszeszorozzuk azon r -ket, melyekre p − 1 binaris ´ oj ´ aban ´ ´ ek ´ u˝ bit 1. reprezentaci az i-edik helyiert


137 / 184

´ Pratt tetele ´ ıtas ´ All´ ˝ ˝ ˝ hogy eljuthatunk-e n-ben polinom idoben ellenorizhet o, ˝ az 1-be qi -kkel valo´ osztasok ´ ´ evel, ´ p − 1-bol seg´ıtseg ahol ´ egyszer felhasznaljuk. ´ minden egyes qi -t legalabb ´ a´ n-ben polinom idoben ˝ ˝ Tovabb ellenorizhet o˝ az is, hogy minden (p−1)/q i ´ enyes-e ´ ˝ ´ i-re erv az r 6≡ 1 mod p egyenlotlens eg. ´ mert valahanyszor ´ De (r, q1 , . . . , qk ) nem teljes bizony´ıtek, ´ at ´ kell adni, hogy qi pr´ım. qi 6= 2, annak is bizony´ıtek ´ A teljes bizony´ıtek: C(p) = (r, q1 , C(q1 ), . . . , qk , C(qk )), ´ voltanak ´ ´ (ez ures, ahol C(qi ) a qi pr´ımszam bizony´ıteka ¨ ha qi = 2).


138 / 184

´ Pratt tetele ´ ıtas ´ All´ ´ hossza O(n2 ). A teljes bizony´ıtek

´ ıtas ´ All´ ´ helyessege ´ ˝ Adott p-re a C(p) bizony´ıtek n-ben polinom idoben ˝ ˝ leellenorizhet o.

´ Bizony´ıtas ´ ld. konyv. ¨ A fentiek alapjan,

´ (M. Agrawal, N. Kayal, N. Saxena, 2002) Tetel


PRÍMEK ∈ P.

139 / 184

´ any ´ tovabbi ´ ´ a P es ´ NP osztalyokr ´ ´ Neh eredmeny ol ´ Tetel ´ Ha P 6= NP, akkor letezik olyan L ∈ NP − P, mely nem NP-teljes.

NPC NPI

vagy

P = NP

P

NPC: NP-teljes nyelvek (NP-complete) NPI: azon (NP − P)-beli nyelvek, amelyek nem NP-teljesek (NP-intermediate). ´ ´ Bonyolultsagelm elet

140 / 184

´ ´ Orakulumos Turing-gep Defin´ıcio´ ´ determinisztikus vagy nemdeterminisztikus Az M ? orakulumos, ´ olyan tobbszavas ¨ ´ mely rendelkezik egy Turing-gep Turing-gep, ´ ´ ´ ´ specialis kerdes szoval (szalaggal), valamint q? , qigen , qnem ´ allapotokkal.

Defin´ıcio´ ´ ´ ec ´ eje. ´ Ekkor az M A Turing-gep, Legyen A ⊆ Σ∗ , ahol Σ az M ab ´ ´ ¨ az A nyelvvel realizaljuk, ugy ´ muk ˝ odik, melyben az orakulumot ¨ ons ¨ eges ´ ´ kiveve, ´ ´ mint egy koz Turing-gep, ha a q? allapotban ´ ´ annak van. Ekkor a qigen vagy a qnem allapotba megy at ˝ ´ es ´ szo´ az A nyelvben van-e. megfeleloen, hogy a kerd

˝ ´ Idobonyolults ag ´ es ´ egyetlen lep ´ esnek ´ ¨ ons ¨ eges ´ Mint a koz esetben, minden kerd ´ ıt. szam´ ´ ´ Bonyolultsagelm elet

141 / 184

´ ´ Orakulumos Turing-gep Defin´ıcio´ ´ osztaly, ´ A tetszoleges ˝ Legyen C bonyolultsagi nyelv. ¨ ˝ ugyanolyan t´ıpusu´ C A : Azon nyelvek, amelyek eldonthet oek ´ ´ ´ ´ asa ´ orakulumos Turing-geppel az orakulum A-val valo´ realizal ´ ¨ o˝ Turing-gepek. ´ mellett, mint a C osztalyba eso˝ nyelveket eldont ´ osztaly. ´ Ekkor Legyen C ′ is bonyolultsagi [ ′ CC = CA. A∈C ′

´ Pelda ◮

PP = P

◮

NP ∪ coNP ⊆ PNP = PSAT


142 / 184

´ ´ Orakulumos Turing-gep ´ Tetel ´ Van olyan A orakulum, melyre PA = NPA .

Lemma ´ Ha A ∈ PSPACE, akkor PA ⊆ PSPACE es NPA ⊆ NPSPACE = PSPACE.

Lemma Ha A PSPACE-teljes, akkor PSPACE ⊆ PA .

´ bizony´ıtasa ´ A tetel ´ obb ˝ ´ fogjuk, hogy ilyen A Legyen A PSPACE-teljes, kes latni ´ letezik. Ekkor:


PSPACE ⊆ PA ⊆ NPA ⊆ PSPACE.

143 / 184

´ ´ Orakulumos Turing-gep

´ Tetel Van olyan B, melyre PB 6= NPB . ´ a P 6= NP sejtes ´ csak olyan gondolatmenettel Tehat ´ mely nem relativizalhat ´ ˝ ´ bizony´ıthato, o´ tetszoleges orakulumra.


144 / 184

´ Logaritmikus tar ´ Tetel ˝ EG ´ ´ problema ´ Az ELERHET OS NL-teljes.

´ Bizony´ıtas ´ tudjuk, hogy a problema ´ Azt mar NL-ben van. Legyen most az ¨ ´ ´ L egy NL-beli nyelv. Ekkor L eldonthet o˝ egy N, log n tarkorl atos ´ nemdeterminisztikus lyukszalagos Turing-geppel. ´ ok ´ szama ´ Egy n hosszu´ x bemeneten a konfiguraci O(nk ) ˝ hogy csak egy elfogado´ konfiguraci ´ o´ valamely k-ra. Felteheto, van. ˝ EG ´ ´ egy Így a konfiguraci ´ os ´ grafot ´ tekintve az ELERHET OS ´ any ´ ahoz ´ ´ csak akkor igen peld ´ any, ´ peld jutunk, mely akkor es ha x ∈ L. ´ os ´ graf ´ elkesz´ ´ ıtheto˝ logaritmikus tarral, ´ Mivel a konfiguraci ´ keszen vagyunk. ´ ´ Bonyolultsagelm elet

145 / 184

´ Logaritmikus tar

¨ ´ Kovetkezm eny ´ ´ problema ´ Az ELERHETETLENS EG NL-teljes.

´ Bizony´ıtas NL = coNL


146 / 184

´ Tetel ´ A 2SAT problema NL-teljes.

´ Bizony´ıtas ´ tudjuk, hogy 2SAT ∈ NL. Tekintsuk Azt mar ¨ az ´ ´ ´ any ´ at. ´ Az eloz ˝ o˝ tetel ´ bizony´ıtasa ´ ELERHETETLENSEG egy peld ˝ hogy az adott graf ´ kormentes. ¨ miatt felteheto, ´ ´ A 2SAT azon ϕ Minden csucshoz ´ rendeljunk ¨ egy x valtoz ot. ´ any ´ at ´ kesz´ ´ ıtjuk ¨ ´ all, ´ ahol peld ¨ el, mely az osszes ¬x ∨ y tagokbol ´ tovabb ´ a´ az s es ´ ¬t tagokbol, ´ ahol s a kezdocs ˝ ucs ´ ta (x, y) el, ´ es ´ cel. Így ϕ kieleg´ ´ ıtheto˝ ⇔ s-bol ˝ nem erhet ´ o˝ el t. ´ ıto˝ kiert ´ ekel ´ ese. ´ Tegyuk ¨ fel, hogy T a ϕ kieleg´ Ekkor T(x) = 1, ´ ´ ´ ˝ es ´ T(t) = 0. Igy t nem erhet ´ valahanyszor x elerhet o˝ s-bol, o˝ el. ´ ˝ Legyen T azon Tegyuk ¨ fel, hogy t nem erhet o˝ el s-bol. ´ ekel ´ es, ´ melyre T(x) = 1 akkor es ´ csak akkor, ha x elerhet ´ kiert o˝ ˝ Ekkor T kieleg´ ´ ıti ϕ-t. s-bol.


147 / 184

´ o´ Turing-gep ´ Alternal Defin´ıcio´ ´ o´ Turing-gep ´ olyan N = (K, Σ, ∆, s) Az alternal ´ melyben K a KES ´ KVAGY nemdeterminisztikus Turing-gep, ´ es ´ ´ amelynek minden szam´ ´ ıtasi ´ diszjunkt halmazok egyes´ıtese, es ´ ˝ hogy a gep ´ pontos). sorozata veges (felteheto, ´ ıtasi ´ faj ´ at ´ az x bemeneten. Tekintsuk ¨ az N szam´ ´ ul ´ ha ´ o´ veg ¨ elfogado, Azt mondjuk, hogy egy C konfiguraci ◮ C-ben a gep ´ ,,igen” allapotban ´ van, vagy ◮

◮

¨ ´ ´ ´ minden kozvetlen leszarmazottja KES van, es ´ -allapotban ´ ul ´ vagy veg ¨ elfogado, ´ ´ valamely kozvetlen ¨ KVAGY -allapotban van, es ´ ´ ul ´ leszarmazottja veg ¨ elfogado.

´ akkor fogadja el az x bemenetet, ha a kezdo˝ Az N gep ´ o´ veg ´ ul ´ kul ¨ konfiguraci ¨ elfogado, ¨ onben elutas´ıtja azt. Az f (n) ˝ ´ ´ ´ ´ ertelemszer ´ ido- vagy tarkorlatos Turing-gep fogalmat uen ˝ ´ definialjuk. ´ ´ Bonyolultsagelm elet

148 / 184

´ o´ Turing-gep ´ Alternal Defin´ıcio´ ´ fuggv ´ ´ Legyen f (n) megengedett bonyolultsagi ¨ eny. (Ido˝ eseten f (n) > n.) ¨ ˝ ´ ´ o´ ATIME(f (n)): az osszes f (n) idokorl atos alternal ´ ¨ ˝ Turing-geppel eldontheto nyelvek. ¨ ´ ´ ´ o´ ASPACE(f (n)): az osszes f (n) tarkorl atos alternal ´ ¨ Turing-geppel eldonthet o˝ nyelvek. AL = ASPACE(log n) AP = ATIME(nk ) ´ ´ Vilagos, hogy NTIME(f (n)) ⊆ ATIME(f (n)) es NSPACE(f (n)) ⊆ ASPACE(f (n)).


149 / 184

AL = P

´ Tetel AL = P.

´ Bizony´ıtas ´ ´ OZAT-KI ´ EKEL ´ ´ problema ´ ´ Lattuk, hogy a HAL ERT ES P-teljes. ´ ´ OZAT-KI ´ EKEL ´ ´ is ´ aban ´ ´ a MONOTON-HAL Valoj mar ERT ES ´ ´ ´ ozat ´ P-teljes, mert minden valtoz omentes hal monotonna´ ˝ teheto. ´ osztaly ´ zart ´ a visszavezetesre, ´ Mivel mindket AL = P teljesul, ¨ ´ ´ ´ ´ ´ ha a MONOTON-HALOZAT-KIERTEKELES AL-teljes.


150 / 184

P ⊆ AL ´ Tetel ´ ´ OZAT-KI ´ EKEL ´ ´ ∈ AL. MONOTON-HAL ERT ES

´ Bizony´ıtas ´ ozat ´ ´ ekel ´ es ´ et ´ kezdje az alternal ´ o´ Adott monoton hal kiert ´ a kimeneti kapunal. ´ Turing-gep ´ ekel ´ esnek ´ ´ Ha ez igaz vagy hamis, a kiert vege. ´ ´ ´ ES-allapotba, ´ ¨ Ha ES-kapu, akkor a gep kul ¨ onben ´ ´ es ´ nemdeterminisztikusan a ket ´ os ˝ VAGY-allapotba lep, ´ el ´ folytatja a kiert ´ ekel ´ est. ´ valamelyiken ´ ul ´ ,,igen” allapotba, ´ ¨ Ha veg ¨ igaz kapuhoz er, kul ¨ onben ,,nem” ´ ´ allapotba megy at. ¨ ´ kapu sorszam ´ at ´ kell tarolni. ´ Ekozben mindig csak az aktualis


151 / 184

AL ⊆ P ´ Tetel ´ ´ OZAT-KI ´ EKEL ´ ´ problema ´ ´ A MONOTON-HAL ERT ES AL-nehez.

´ Bizony´ıtas ˝ Megmutatjuk, hogy tetszoleges L ∈ AL nyelv visszavezetheto˝ a ´ ´ ´ ´ ´ MONOTON-HALOZAT-KIERTEKELES-re. ´ o´ Turing-gep, ´ Legyen N = (K, Σ, ∆, s) olyan pontos, alternal ´ ¨ az L nyelvet. Felteheto, ˝ hogy minden mely log n tarral eldonti ´ onak ´ ´ nem elfogado´ vagy elutas´ıto´ konfiguraci 2 leszarmazottja ´ os ´ graf ´ adott x bemenet eseten ´ kormentes. ¨ van. A konfiguraci Minden C csucsot ´ helyettes´ıtunk ¨ egy C′ kapuval. Ez ´ kapu, ha az allapot ´ ES KES ´ -ben van, ´ VAGY kapu, ha az allapot KVAGY -ban van, ´ igaz kapu, ha az allapot ,,igen”, ´ hamis kapu, ha az allapot ,,nem”.


152 / 184

AL ⊆ P

¨ ´ ´ C2 , akkor a Amennyiben C kozvetlen leszarmazottai C1 es ´ C2′ . A kimeneti csucs ˝ ´ ozatban ´ ´ a C1′ es hal C′ osei ˝ ´ o. ´ kezdokonfigur aci ´ ´ ozat ´ ´ eke ´ akkor es ´ csakis akkor igaz, ha Vilagos, hogy a hal ert x ∈ L. ´ o´ merete ´ ¨ ´ ´ hogy Minden konfiguraci O(log n). Így konnyen lathat o, ´ ozat ´ ´ ıtheto˝ logaritmikus tarral. ´ a hal elkesz´

´ Tetel Ha f (n) ≥ log n megengedett, akkor ASPACE(f (n)) = TIME(kf (n) ).


153 / 184

´ tar ´ A polinomialis

QSAT ´ Boole-formula prenex Adott: ∃x1 ∀x2 . . . Qm xm ϕ kvantifikalt ´ ´ normalalakban ugy, ´ hogy a ϕ konjunkt´ıv normalalak u´ kvantormentes formula, melyben legfeljebb az x1 , . . . , xm ´ ´ fordulnak elo. ˝ valtoz ok ´ es: ´ Igaz-e az adott formula? Kerd

´ Megjegyzes ◮ ◮

´ asa ´ nem lenyeges. ´ A kvantorok szigoru´ alternal ´ Az sem lenyeges, hogy az elso˝ kvantor ∃.


154 / 184

´ ıtas ´ All´ ´ A QSAT problema PSPACE-ben van.

´ Bizony´ıtas ˝ O(m) tarral ´ Legyen adott a ∃x1 ∀x2 . . . Qm xm ϕ formula. Ebbol ´ ıtunk ´ ozatot, ´ ´ egy m melys ´ eg ´ u, elkesz´ ¨ egy olyan hal mely grafja ˝ ´ fa. kiegyensulyozott ´ binaris ◮ Paratlan ´ szinten: VAGY kapu ´ kapu ◮ Paros ´ szinten: ES ◮

´ igaz vagy hamis attol ´ fugg ˝ ˝ Level: ¨ oen, hogy a ,,megfelelo” ´ ekel ´ es ´ mellett ϕ igaz vagy hamis. kiert

´ eggel ´ ´ ´ O(m) Egy rekurz´ıv algoritmussal a melys aranyos, tehat ´ ´ ekelj ´ ´ ozatot. ´ tarral kiert uk ¨ a hal ´ tranzitivitas ´ anak ´ ´ aban ´ A visszavezetes bizony´ıtas megismert ´ ´ algoritmust osszetehetj ¨ modszer szerint a ket uk ¨ – O(m) ´ ´ ´ tarkorl atos Turing-gepet kapunk. ´ ´ Bonyolultsagelm elet

155 / 184

´ Megjegyzes ´ A problema akkor is PSPACE-ben van, ha ◮ ϕ tetszoleges ˝ kvantormentes Boole-formula.

◮

´ ´ a kvantorok nem feltetlen ul ¨ valtakoznak. ´ ´ ´ valtoz ´ ´ is ϕ-ben az x1 , . . . , xm valtoz okon k´ıvul ¨ egyeb ok ˝ ´ azt kerdezz ´ ´ ıtheto-e ˝ az egesz ´ elofordulnak, es uk, ¨ kieleg´ formula. ´ a formula nem feltetlen ul ¨ prenex alaku. ´

◮

´ azt kerdezz uk, ¨ hogy a formula hamis-e.

◮ ◮


156 / 184

´ Tetel ´ A QSAT problema PSPACE-teljes.

´ Bizony´ıtas ´ ´ csakis Mivel PSPACE = coPSPACE, a QSAT problema akkor es akkor PSPACE-teljes, ha QSAT-KOMPLEMENTER PSPACE-teljes. ´ ´ ´ csakis akkor PSPACE-teljes, ha a Ez utobbi problema akkor es ´ QSAT azon valtozata PSPACE-teljes, melyben az adott formula ´ magja (a ϕ a ∃x1 ∀x2 . . . Qm xm ϕ formulaban) diszjunkt´ıv ´ ´ normalformaban van. ′ ¨ az O(nk ) Legyen adott az L ∈ PSPACE nyelv, melyet eldont ´ ´ ´ Adott x, n hosszu´ bemeneten a tarkorl atos M Turing-gep. k ´ ok ´ szama ´ konfiguraci O(2n ) valamely k-ra. ´ kedve´ ert ´ feltesszuk, ´ ok ´ Az egyszerus ˝ eg ¨ hogy a konfiguraci k ´ hogy pontosan egy elfogado´ ´ szama legfeljebb 2n es ´ o´ van. konfiguraci


157 / 184

´ ot ´ kodoljunk ´ Minden konfiguraci egy nk hosszu´ bitsorozattal. Legyen ´ UT(a, b, i) ´ csakis akkor, ha a-bol ´ elerhet ´ akkor es o˝ a b legfeljebb 2i hosszu´ uton. ´ Megmutatjuk, hogyan lehet fel´ırni olyan ψi (A, B) ´ az A = {a1 , . . . , ank }, B = {b1 , . . . , bnk } szabad formulat ´ ´ ´ csakis akkor igaz a valtoz ´ ´ valtoz okkal, hogy ψi akkor es ok ´ ekel ´ ese ´ mellett, ha a valtoz ´ ´ ert ´ ekei ´ valamely kiert ok olyan a, b ´ ´ okat ´ ´ konfiguraci kodolnak, hogy UT(a, b, i) teljesul. ¨ Így x ∈ L ⇔ ψnk (A, B) igaz, amikor A helyebe ´ a kezdo˝ ´ ot, ´ B helyebe ´ ´ ot ´ kodol ´ o´ konfiguraci az elfogado´ konfiguraci ´ ekel ´ est ´ helyettes´ıtjuk. kiert ¨ ´ logaritmikus tarral ´ ´ ıthetok ˝ lesznek. A formulak elkesz´ ´ ´ Bonyolultsagelm elet

158 / 184

A konstrukcio´ ψ0 (A, B): azt fejezi ki, hogy minden i-re ai = bi vagy a B ´ o´ egy lep ´ esben ´ ¨ ´ konfiguraci kovetkezik A-bol. 2k ´ formulaval, ´ Megadhato´ O(n ) hosszu´ kvantifikalt aminek a ´ magja diszjunkt´ıv normalalak u. ´ ψi+1 (A, B) : ∃Z(ψi(A, Z) ∧ ψi (Z, B)). ´ exponencialisan ´ A formulak hosszuak ´ lesznek! ψi+1 (A, B): ∃Z∀X∀Y ((X = A ∧ Y = Z) ∨ (X = Z ∧ Y = B)) → ψi (X, Y) .

˝ hozhatoak. ´ ´ ´ ψi kvantorai elore A mag diszjunkt´ıv normalform aja ´ ´ ´ plusz egy O(n2k ) hosszu´ tag. normalform aja, ψi magjanak


159 / 184

¨ ´ igazolunk az alternal ´ o´ polinom ido˝ es ´ a Most egy osszef ugg ¨ est ´ tar ´ koz ¨ ott. ¨ polinomialis ´ definialtuk ´ ´ Mar az AP = ATIME(nk ) osztalyt.

´ Tetel ´ A QSAT problema AP-teljes.

´ Bizony´ıtas ´ ahoz: ´ ´ o´ Turing-gep ´ egymas ´ A QSAT ∈ AP bizony´ıtas egy alternal ´ megsejti az x1 , x2 , . . . valtoz ´ ´ ert ´ ek ´ et, ´ az utan ok ´ ´ valtoz ´ ´ et ´ KVAGY allapotban, ´ egzisztencialisan kvantifikalt ok az ´ ´ valtoz ´ ´ et ´ KES ´ ´ ul univerzalisan kvantifikalt ok Veg ¨ ´ allapotban. ˝ ´ kiert ´ ekel ´ es ´ kieleg´ ´ ıti-e a formula ellenorzi, hogy a megtalalt ´ magjat. ˝ eny: ´ ´ Idoig polinomialis.


160 / 184

´ Teljesseg ´ bizony´ıtas ´ anak ´ ´ A Cook-tetel valtozata. A nemdeterminisztikus ´ ´ ´ ´ ¨ uk valaszt asokhoz tartozo´ valtoz okat lekotj ¨ ∃ vagy ∀ kvantorral ´ aszerint, hogy az allapot a KVAGY vagy KES ´ halmazba esik-e. ˝ hogy csak alternalnak ´ ´ Felteheto, – minden masodik azonosan ´ kvantifikalt.

¨ ´ Kovetkezm eny AP = PSPACE.

´ Bizony´ıtas ´ osztaly ´ zart ´ a visszavezetesre ´ ´ QSAT mindkettoben ˝ Mindket es teljes.


161 / 184

´ ´ ´ ekok ´ Ketszem elyes jat

´ ´ ´ ekk ´ ent: ´ elyes jat A QSAT felfoghato´ ketszem ◮ Jat ´ ekosok: ´ ∃, ∀ ◮

´ esek ´ ´ ´ eke, ´ ´ eke, ´ Lep felvaltva: x1 ert x2 ert ... ´ ´ ıteni a formula magjat ´ ∃ celja: kieleg´

◮

´ ∀ celja: hamissa´ tenni

◮


162 / 184

¨ ´ EK ´ FOLDRAJZI JAT ´ ıtott graf, ´ 1 kezdocs ˝ ucs. Adott: G = (V, E) irany´ ´ ´ es: ´ Az I. jat ´ ekos ´ ´ ´ ekban? ´ Kerd nyer-e az alabbi jat ◮ ◮

◮

´ ekos ´ ´ evel. ´ Az I. jat kezd az 1 csucs ´ megnevezes ´ esben ´ ´ ekosnak ´ Minden lep minden jat egy olyan csucsot ´ ´ ´ nem szerepelt, es ´ amelybe kell valasztani, amely meg ´ az eloz ˝ oleg ˝ ´ vezet el megnevezett csucsb ´ ol. ´ ekos ´ ´ ul Egy jat vesz´ıt, ha veg ¨ nem tud ilyen csucsot ´ megnevezni.


163 / 184

´ ıtas ´ All´ ¨ ´ EK ´ problema ´ A FOLDRAJZI JAT PSPACE-ben van.


´ essorozatok ´ ´ eben ´ A lep hossza a bemenet meret ´ polinomialis.

´ ´ eny ´ u˝ algoritmus, mely adott Letezik olyan polinom tarig ´ asra ´ ´ az all ´ as ´ rak ´ ovetkez ¨ ˝ vagy ha ilyen all megkonstrualja oit, ¨ ´ ekos ´ nincs, eldonti, melyik jat nyert. ´ ´ ´ ek ´ PSPACE-ben van: Minden ilyen ketszem elyes jat ◮

◮ ◮

´ ´ ıtjuk ´ ek ´ faj ´ at. ´ Polinom tarral elkesz´ ¨ az adott jat ´ eggel ´ ´ ´ ¨ uk, Melys aranyos tarral eldontj ¨ kinek van nyero˝ ´ aja. ´ strategi

´ algoritmus osszetehet ¨ ˝ polinom tarkorl ´ ´ A ket o: at.

´ ıtas ´ All´ ¨ ´ EK ´ problema ´ A FOLDRAJZI JAT PSPACE-teljes.


164 / 184


∃x∀y∃z∀u(y ∨ ¬x) ∧ (y ∨ z) ∧ (¬y ∨ u) ∧ (¬x ∨ ¬y) 1 x

¬x

y

¬y

z

¬z

u

¬u

165 / 184

◮

´ ekos ´ ¨ el az egzisztencialisan, ´ ´ Az elso˝ jat donti a masodik az ´ ´ valtoz ´ ´ ek ´ et, ´ mely a c´ımkevel ´ univerzalisan kvantifikalt o´ ert ´ ellentetes.

◮

´ ´ ekos ´ ´ A masodik jat valaszt egy tagot. ´ ekos ´ ´ csak akkor nyer, ha a tag Az elso˝ jat akkor es ´ igaz (visszavezeto˝ el ´ valaszthat ´ ´ valamely literalja o).

◮

◮

´ ekos ´ Mivel ez minden tagra igaz, az elso˝ jat nyer ⇔ a formula igaz.


166 / 184

´ HELYBEN ELFOGADAS ´ es ´ x bemeno˝ szo. ´ Adott: M determinisztikus Turing-gep ´ es: ´ Elfogadja-e M az x-et ugy, Kerd ´ hogy szava valamikor is hosszabb lenne, mint |x| + 1?

´ Tetel ´ problema ´ A HELYBEN ELFOGADAS PSPACE-teljes.

´ ´ ´ REGULARIS KIFEJEZESEK EKVIVALENCIAJA ´ regularis ´ kifejezes. ´ Adott: Ket ´ es: ´ Ugyanazt a nyelvet jelolik-e? ¨ Kerd

´ Tetel ´ ´ ´ ´ A REGULARIS KIFEJEZESEK EKVIVALENCIAJA problema PSPACE-teljes.


167 / 184

´ ´ EKVIVALENCIAJA ´ VEGES AUTOMATAK ´ ´ M2 veges ´ Adott: M1 es nemdeterminisztikus automatak. ´ es: ´ M1 es ´ M2 ekvivalensek-e? Kerd

´ Tetel ´ ´ EKVIVALENCIAJA ´ ´ A VEGES AUTOMATAK problema PSPACE-teljes.


168 / 184

´ Tul ´ a PSPACE osztalyon

Defin´ıcio´ k

EXP = TIME(2n ) k NEXP = NTIME(2n ) ´ ´ tudjuk, hogy PSPACE ⊆ EXP. Vilagos, hogy EXP ⊆ NEXP es ´ NEXP osztalyok ´ Nem ismert, hogy az EXP es megegyeznek-e.

´ Tetel Ha P = NP, akkor EXP = NEXP.


169 / 184

´ ¨ or ¨ reprezentaci ´ oja ´ Grafok tom ◮ ◮ ◮

G = (V, E), V = {0, 1, . . . , 2m − 1} ´ ´ Boole-fuggv ´ Megadhato´ egy f (~x,~y), 2m-valtoz os ¨ ennyel. Az f megadhato´ egy 2m bemeneti kapuval rendelkezo˝ ´ ozattal. ´ hal

´ ozatok ´ ´ ´ tom ¨ oren. ¨ Hal hasonlo´ modszerrel megadhatok

´ Tetel ¨ OR ¨ HAMILTON-UT ´ es ´ A TOM ¨ OR ¨ HAL ´ ˝ EG ´ OZAT-KIEL ´ ÍTHETOS ´ problem ´ ak ´ TOM EG NEXP-teljesek.

´ Tetel ¨ OR ¨ HAL ´ ´ OZAT-KI ´ EKEL ´ ´ problema ´ A TOM ERT ES EXP-teljes.


170 / 184

Defin´ıcio´ k

EXPSPACE = SPACE(2n ) ´ Vilagos, hogy NEXP ⊆ EXPSPACE.

´ Tetel ´ ´ ´ regularis ´ Az alabbi problema EXPSPACE-teljes: adott ket ´ melyekben negyzetreemel ´ ´ is szerepelhet, kifejezes, es ´ ekvivalensek-e a kifejezesek?


171 / 184


R 2EXP EXPSPACE

coNEXP

NEXP

EXP PSPACE

coNP NP

P

172 / 184

´ szam´ ´ ıtasok ´ Randomizalt

´ ÍTAS ´ PAROS ´ ´ ahol Adott: G = (U, V, E) paros graf, U = {u1 , . . . , un }, V = {v1 , . . . , vn }, E ⊆ U × V ´ es: ´ Letezik-e ´ ´ ´ azaz olyan M ⊆ E Kerd teljes paros´ ıtas, halmaz, hogy


∀ui ∃!vj

(ui , vj ) ∈ M

∀vj ∃!ui

(ui , vj ) ∈ M?

173 / 184

´ Szimbolikus determinans ´ Legyen AG az az n × n-es matrix, melynek (i, j)-dik eleme az xi,j ´ ´ ha (ui , vj ) ∈ E, 0 kul ¨ valtoz o, ¨ onben.

´ ıtas ´ All´ ´ akkor es ´ csakis akkor nem A det(AG ) szimbolikus determinans ´ ´ ´ nulla, ha letezik teljes paros´ ıtas.


det(AG ) =

P

σ(π)

π

◮

∀π :

n Q

i=1 ◮

n Q

i=1

´ ´ AG i,π(i) 6= 0 ⇔ π teljes paros´ıtas.

π1 6= π2 , 6= 0 ⇒

n Q

i=1

nem fordul elo˝

n Q

i=1 ´ ´ Bonyolultsagelm elet

AG i,π(i) .

´ ´ AG i,π1 (i) tartalmaz olyan valtozot, mely

AG i,π2 (i) -ben. 174 / 184

Lemma ´ ´ nem azonosan nulla, Legyen π(x1 , . . . , xm ) adott m-valtoz os, ´ ´ aban ´ ´ legyen minden valtoz oj legfeljebb d-ed foku´ polinom, es m M > 0. Ekkor azon (x1 , . . . , xm ) ∈ {0, 1, . . . , M − 1} rendezett ´ m-esek szama, melyekre π(x1 , . . . , xm ) = 0, legfeljebb mdM m−1 .

´ Bizony´ıtas ´ m szerinti teljes indukcioval. ´ m = 1: Legfeljebb d zerushely. m > 1: Legyen π(x1 , . . . , xm )

=

p0 (x1 , . . . , xm−1 )xrm + p1 (x1 , . . . , xm−1 )xr−1 m +

. . . + pr (x1 , . . . , xm−1 ). Tegyuk ¨ fel, hogy (x1 , . . . , xm ) ∈ {0, 1, . . . , M − 1}m , melyre π(x1 , . . . , xm ) = 0. (a) p0 (x1 , . . . , xm−1 ) = 0 ⇒ (m − 1)dM m−2 · M (b) p0 (x1 , . . . , xm−1 ) 6= 0 ⇒ dM n−1

¨ Osszesen: mdM m−1 . ´ ´ Bonyolultsagelm elet

175 / 184

¨ ´ Kovetkezm eny ˝ o˝ feltetelek ´ ´ ha M = 2m es ´ d = 1, akkor azon Az eloz eseten, m ´ (x1 , . . . , xm ) ∈ {0, 1, . . . , M − 1} rendezett m-esek szama, m ¨ melyekre π(x1 , . . . , xm ) = 0, legfeljebb M2 , azaz az osszes m-esek fele.

´ ÍTAS-ra ´ ´ algoritmus PAROS Randomizalt ´ ´ ´ szamokat ´ 1. Valasszunk veletlenszer uen ˝ i1 , . . . , im egesz a ´ ahol m az elek ´ ´ {0, 1, . . . , 2m − 1} halmazbol, szama. ´ ıtsuk ki Gauss eliminaci ´ oval ´ 2. Szam´ a det(AG (i1 , . . . , im )) ´ eket. ´ ert ´ ´ ´ ´ igen: letezik teljes paros´ ıtas. 3. Ha ez nem 0, akkor a valasz ´ ınuleg) ´ ¨ ´ nem: G-ben (valosz´ ˝ nem letezik 4. Kul ¨ onben a valasz ´ ´ teljes paros´ ıtas.


176 / 184

´ Megjegyzes ◮ ◮ ◮

◮

´ ´ Igen valasz sohasem teves. ´ ´ a teved ´ ´ valosz´ ´ ınus ´ Nem valasz eseten es ˝ ege ≤ 1/2. Így k-szori megismetl ´ es ´ eseten ´ nem valasz ´ ´ a eseten k ´ ´ ´ ´ tevedes valosz´ınus ˝ ege ≤ 1/2 . ˝ eny. ´ Polinom idoig


177 / 184

´ A ,,Fermat proba” ´ Tetel ´ es ´ 0 < a < p egesz. ´ Tegyuk ¨ fel, hogy p pr´ımszam Ekkor ap−1 ≡ 1 mod p.

´ Hipotezis ´ ´ Ha n > 1 nem pr´ımszam, akkor a nemnulla a maradekok ´ felere ´ igaz, hogy legalabb an−1 6≡ 1 mod n.

´ ´ polinomideju˝ algoritmus az Adodna egy randomizalt ¨ ´ = PRÍMEK OSSZETETT-SZ AM ´ ara. ´ problem ´ ´ Bonyolultsagelm elet

178 / 184

´ A ,,Fermat proba”

´ Adott n > 2 eseten: ´ ´ ´ 1. Valasszunk ki egy a 6= 0 veletlen maradekot. ¨ ´ szam. 2. Ha an−1 6≡ 1 mod n, akkor n osszetett ´ ınuleg ˝ pr´ım. 3. Ellenkezo˝ esetben n valosz´

´ ´ ´ ınus ´ ´ es ´ Teves (negat´ıv) valasz valosz´ ˝ ege ≤ 1/2, k-szori ismetl k ´ pedig legfeljebb 1/2 . utan ´ De a HIPOTEZIS nem igaz. . .


179 / 184

´ Legendre-szimbolum

Defin´ıcio´ ´ ´ ´ Legyen p paratlan pr´ımszam, az a pedig p nemnulla maradeka. Ekkor az (a | p) = a(p−1)/2 mod p ´ ´ ´ az a es ´ p Legendre-szimbolum anak nevezzuk. ¨ kifejezest

´ ıtas ´ All´ (a | p) ∈ {p − 1, 1}


((a | p) ∈ {−1, 1})

180 / 184

´ Legendre-szimbolum Defin´ıcio´ ´ Legyenek M, N relat´ıv pr´ımek, N paratlan. Legyen N = q1 . . . qk , ahol minden qi pr´ım. Ekkor (M | N) =

k Y (M | qi ). i=1

´ Tetel ´ ¨ ´ Ha N paratlan osszetett szam, akkor az N-nel relat´ıv pr´ım ´ felere ´ teljesul, ´ legalabb ¨ hogy M < N szamok


(M | N) 6= M (N−1)/2 mod N.

181 / 184

Az algoritmus

´ ´ Adott N ≥ 1 paratlan egesz. ´ ´ N − 1 koz ¨ ott ¨ egy veletlen ´ ´ szamot, ´ 1. Generaljunk 1 es egesz legyen ez M. ´ ´ ek ´ et. ´ 2. Szamoljuk ki (M, N) ert ¨ ´ ´ igen: N osszetett szam. 3. Ha (M, N) > 1, akkor a valasz ´ ıtsuk ki (M | N) es ´ M (N−1)/2 mod N 4. Ellenkezo˝ esetben szam´ ´ ek ´ et, ´ majd hasonl´ıtsuk ossze ¨ ´ eredmenyt. ´ ert a ket ◮

◮


´ ´ igen: N osszetett ¨ Ha nem egyeznek meg, a valasz ismet ´ szam. ´ ınuleg ´ nem: N valosz´ ˝ pr´ım. Ellenkezo˝ esetben a valasz

182 / 184

Defin´ıcio´ Legyen L nyelv L-hez tartozo´ polinom ideju, ˝ Monte-Carlo t´ıpusu´ ´ olyan pontos, nemdeterminisztikus, p(n) polinom Turing-gep ´ melynek minden nem vegs ´ o˝ ideju˝ Turing-gep, ´ oj ´ aban ´ ´ nemdeterminisztikus konfiguraci pontosan ket ´ ´ van, es ´ amelyikre teljesul: valaszt asa ¨ ◮ x ∈ L eseten ´ a szam´ ´ ıtasi ´ sorozatok legalabb ´ fele ,,igen” ´ ´ odik. ˝ valasszal vegz ◮

´ ıtasi ´ sorozat ,,nem” valasszal ´ ´ minden szam´ x∈ / L eseten ´ odik. ˝ vegz

Defin´ıcio´ ´ RP: polinom ideju, ˝ Monte-Carlo t´ıpusu´ Turing-geppel ¨ eldonthet o˝ nyelvek.


183 / 184

´ ıtas ´ All´ P ⊆ RP ⊆ NP.

¨ ´ Kovetkezm eny P ⊆ coRP ⊆ coNP.

Defin´ıcio´ ZPP = RP ∩ coRP. ´ Polinom ideju, ˝ Las Vegas-algoritmussal (Turing-geppel) ¨ ´ ak. ´ eldonthet o˝ nyelvek, ill. problem ´ Ha egy ilyen algoritmust k-szor fuggetlen ¨ ul ¨ vegrehajtunk, annak ´ ´ ´ ınus ´ valaszt, legfeljebb valosz´ ˝ ege, hogy nem kapunk vegleges 1/2k . ´ ´ Bonyolultsagelm elet

184 / 184

Bonyolultságelmélet. SZTE Informatikai Tanszékcsoport

Recommend Documents