Számításelmélet 2 - El®adás jegyzet Rózsa Gábor 2007. els® félév
1
Bevezetés
Ajánlott irodalom:
•
Katona-Recski: Bevezetés a véges matematikába
•
Rónyai-Ivanyos-Szabó: Algoritmusok
•
Lovász: Aloritmusok bonyolultsága
Ez a jegyzet arra a kérdésre próbál válaszolni, hogy egy algoritmikus problémánál milyen jelek alapján dönthet® el, hogy van esély gyors programot írni a feladatra, vagy kár is próbálkozni, nem várható gyors eljárás.
(Legtöbbször ez azt jelenti, hogy az egyetlen, amit tehetünk az, hogy szisztematikusan
végignézünk minden esetet.) S®t, amint látni fogjuk, olyan is van, hogy egyáltalán nem lehet egy feladatra algoritmust találni (programot írni). Nagyjából a következ® lehet®ségek szoktak adódni egy algoritmikus probléma vizsgálatakor. 1. Gyors algoritmust találunk és bebizonyítjuk, hogy nincs gyorsabb. 2. Gyors algoritmust találunk és bizonyítunk egy alsó becslést arra, hogy maximum mennyivel lehetne gyorsabb egy ügyesebb algoritmus. 3. Csak lassú algoritmusunk van a problémára, azt sejtjük, hogy nincs is sokkal gyorsabb, de precíz alsó becslést nem tudunk bizonyítani. 4. Bebizonyítjuk, hogy a vizsgált problémára nem lehet algoritmust készíteni. Az els® típusra jó példa lehet a maximum vagy minimum keresés egy adathalmazban páronkénti összehasonlításokkal, illetve a kett® keresése egyszerre. Mindhárom esetben be lehet bizonyítani (amint az el®z® félévben láttuk), hogy a talált algoritmusnál nincs jobb. A második típusra (erre szinte minden eddig tanult eljárás jó példa) példa lehet a sorbarendezés, ahol elég gyors algoritmusunk van és jó alsó becslésünk, de a kett® azért nem egyezik meg. A harmadik fajta jelenségr®l a hátizsák problémánál, illetve a pakolási problémánál tanultunk. Itt az általános esetben csak exponencális algoritmusunk van. Nincs precíz bizonyításunk rá, hogy nem lehetne sokkal gyorsabb eljárást találni, de azt sejtjük, hogy nem. A félév során felépítünk egy elméletet, mely, ha nem is ad precíz bizonyítást, de valószín¶síti, hogy a sejtés igaz. A negyedik esetre korábban nem tanultunk példát, most mutatunk egyet.
Dominó probléma.
Adott egy véges dominókészlet (azaz véges sok féle dominó van, de mindegyikb®l
végtelen darab) és egy kijelölt kezd®domió. Egy dominónak négy oldala van, minden oldalt egy-egy jellel jelöljünk.
Kiválasztunk egy kezd®dominót.
Egy újabb dominót csak úgy lehet lerakni, ha az összes
szomszédos dominóhoz megfelel®en illeszkedik (az illeszked® oldalpároknál ugyanaz a jel szerepel). Kérdés: kirakható-e a kezd®dominóból indulva a teljes sík? Erre a problémára nem lehet algoritmust csinálni (és ezt be is lehet bizonyítani). Például 1212 oldalú dominókkal ki lehet rakni a teljes síkot, de az {1234, 2322} dominókészlettel nem.
De níció (P-beli) Egy probléma polinomiális (P-beli), ha van rá olyan algoritmus, mely n hosszúságú input esetén legfeljebb cn
d
lépést tesz ( c és d konstansok).
A továbbiakban akkor fogunk egy algoritmust gyorsnak gondolni, ha P-beli.
Példa Egész számok összeadása polinomiális probléma.
∈N a+b
Bemenet: a, b Kimenet:
A bemenet hossza:
log2 a + log2 b
Az exponenciális algoritmusokat nem szeretjük, mert nagyon gyorsan n® a lépésszám, ezért nagy lesz a futási id®.
2
MINIMAX tételek
Ebben a fejezetben egy lehetséges magyarázatot adunk arra, hogy egy problémára gyors algoritmus készíthet®. Sok olyan tétel van a matematikában, mely azt mondja ki, hogy egy mennyiség maximuma megegyezik egy másik mennyiség minimumával. Az a tapasztalat, hogy ha a két mennyiségre igaz egy ilyen tétel (ezeket általában MINIMAX tételeknek hívják), akkor található gyors algoritmus, mely megkeresi a maximumot illetve minimumot. Egy ilyet tanultunk korábban:
Példa Intervallumpakolás problémája: adottak I1 , . . . ,In ⊆
R
zárt intervallumok, amelyekb®l maximális számú
diszjunkt intervallumot szeretnénk kiválasztani.
Tétel (Dilworth tétele) A diszjunkt intervallumok maximális száma megegyezik a lefogó pontok minimális számával.
De níció (Lefogó pontok) Néhány pont egy intervallumrendszer lefogó pontrendszerét alkotja, ha minden intervallumban legalább egy pont van közülük. Vegyük észre, hogy az nyilvánvaló, hogy a diszjunkt intervallumok maximális száma legfeljebb akkora, mint a minimális lefogó ponthalmaz elemszáma (azaz "max juk
k)
≤min").
Ha ugyanis találunk néhány (mond-
diszjunkt intervallumot, akkor egy lefogó ponthalmaz legalább
tervallumot is csak legalább
k
k
elem¶, hiszen már ezt a
k
in-
ponttal lehet lefogni (pláne az összeset). Ezek után már elég találni egy
konkrét példát egy lefogó ponthalmazra és ugyanannyi diszjunkt intervallumra, mint ahány pontú a lefogó halmaz. A bizonyítás egy algoritmust ad meg, mely talál ilyeneket. Ez az algoritmus ráaadásul gyors is. Megjegyzés. Az ilyenfajta problémánál két mennyiséget hasonlítok össze.
Az egyik mennyiség mini-
mumáról akarom belátni, hogy nagyobb, mint a másik mennyiség maximuma.
Általában az könnyen
ellen®rizhet®, hogy "max ≤min", így a bizonyításhoz elég találni egy közös értéket. Tehát, ha az a feladatunk, hogy gyors algoritmust keressünk egy mennyiség minimumának meghatározására, akkor sokszor segít, ha találunk egy másik mennyiséget, melynek maximuma is kisebb egyenl® az eredetileg vizsgált mennyiség minimumánál. Ilyenkor abban bízva, hogy igazából a minimum és a maximum megegyezik, sokszor ötletet is kapunk arra, mit csináljon az algoritmus, hogy megtalálja a közös értéket. A továbbiakban ilyen példákat mutatunk.
2.1
Gráfparaméterek és összefüggéseik
G = (V, E)
gráfban vizsgáljuk a következ®ket.
De níció (lefogó ponthalmaz) V0 ⊆ V
lefogó ponthalmaz, ha minden él egyik végpontját tartalmazza. (Például: hogyan helyezzünk el
rend®röket egy város térképén, hogy minden utcát tudjanak gyelni?) A legkisebb lefogó ponthalmaz jele:
τ (G).
De níció (független élhalmaz (párosítás)) E0 ⊆ E
független élhalmaz, ha bármely két
A legnagyobb független élhalmaz jele:
E 0 -beli
élnek nincs közös végpontja.
ν(G).
De níció (független ponthalmaz) V0 ⊆V
független ponthalmaz, ha a
V 0 -beli csúcsok α(G).
A legnagyobb független ponthalmaz jele:
között nincs él.
De níció (lefed® élhalmaz) E0 ⊆ E
V -beli ρ(G).
lefed® élhalmaz, ha minden
A legkisebb lefed® élhalmaz jele:
csúcs egy
E 0 -beli
él végpontja.
Tétel (Gallai tételei) 1.
α(G) + τ (G) = v(G)
hurokél nélküli
G-ben. (v(G)
2.
ν(G) + ρ(G) = v(G)
izolált pont nélküli
a csúcsok száma.)
G-ben.
Példa 3
Ha a gáf a
csúcsú teljes gráf, azaz a háromszög, akkor
α = 1, ρ = 2, τ = 2, ν = 1.
A továbbiakban algoritmust keresünk a fenti négy mennyiség meghatározására egy gráfban. Vegyük észre, hogy a négy mennyiség (két min és két max) esélyt ad rá, hogy minimax tételt és így (valószínüleg) gyors algoritmust találjunk. gráfban teljesül
ν≤τ
és
Könny¶ ugyanis ellen®rizni, hogy bármely hurokél és izolált pont nélküli
α ≤ ρ.
Az els® egyenl®tlenséghez azt kell észrevenni, hogy ha van a gráfban
független él, akkor már ezeket sem lehet lefogni
k -nál
mindent külön-külön ponttal foghatjuk csak le), hát még, ha az összeset akarjuk lefogni. látható, hogy jelöltünk:
ha
k független pont α = ρ és ν = τ
lefedéséhez legalább
k
kevesebb ponttal (hiszen nincs közös végpontjuk,
k
élre van szükség.
Hasonlóan
Tehát van két minimax tétel
igaz lenne, akkor valószínüleg lenne gyors algoritmusunk mind a négy
paraméter meghatározására. Ez azonban általában nem igaz, amint a fenti példa is jelzi. Páros gráfokra viszont mindkett® teljesül és van is gyors algoritmus.
Tétel (König tétele) Páros gráfban
α=ρ
és
ν = τ.
Bizonyítás. Az alábbiakban ismertetend® algoritmus, melyet
Magyar módszer
nek hívnak, megtalálja
mind a négy speciális, fent de niált halmazt. Pontosabban megad egy lefogó ponthalmazt és egy független élhalmazt, melyek mérete megegyezik, illetve egy lefed® élhalmazt és egy független ponthalmazt, melyek mérete szintén egyenl®. A tétel el®tti bekezdés alapján ez automatikusan biztosítja, hogy a talált halmazok maximálisak illetve minimálisak és, hogy a két minimax tétel igaz. Legyen kezdetben
G = (A ∪ B, E) páros gráf. Minden F = ∅. Két lépést ismételgetünk.
1. keresünk olyan 2. javító úton
F -be
1
a nem
e ∈ E\F
élet, melyre
javítunk. (Ha
F -belieket,
pillanatban van egy
F ∪ {e}
független élrendszerünk,
is független élrendszer.
v1 , . . . , vk javító út, F elemszáma
eggyel n®
F ⊆ E
akkor kidobva
F -b®l
az út
F -beli
éleit és berakva
és továbbra is független élhalmaz marad.)
Az algoritmus megáll, ha egyik lépés sem megy. Tegyük fel, hogy leállt az algoritmus és tekintsük a következ® felosztását a gráf csúcsainak.
X1 := {a ∈ A|a nincs fedve F -belivel }, Y1 := {b ∈ B|b nincs fedve F -belivel }, X2 := {a ∈ A \ X1 |a elérhet® alternáló úton X1 -beli csúcsból }, Y2 az X2 elemeinek X3 := a maradék A-beli, Y3 az X3 elemeinek párjai. Hol lehet éle G-nek? X1 − Y1 nem lehet, mert nem ment az 1. lépés. X1 − Y2 lehet. X1 − Y3 nem lehet, mert akkor találnánk alternáló utat egy X3 -belibe. X2 − Y1 nem lehet, mert nem ment a 2. lépés (javítás). X2 − Y2 lehet. X2 − Y3 nem lehet, mert akkor X3 -belibe lenne alternáló út. X3 − Y1 lehet. X3 − Y2 lehet. X3 − Y3 lehet.
párjai,
Ezek alapján könnyen ellen®rni a következ®ket.
1 alternáló
F -beli
út: ha egy gráfban meg van adva egy
és nem
F -beli
F
független élhalmaz, akkor az olyan utat, melyben felváltva szerepelnek
élek, alternáló útnak hívjuk
javító út: olyan alternáló út, aminek kezd® és végpontja
F
által fedetlen pont
X1 ∪ X2 ∪ Y1 ∪ Y3
független ponthalmaz.
Lefed® élhalmazt kapunk, ha vesszük az
F -beli éleket és 1-1 élt az Y1 és X1 -beli cúcsokon.
(Ez ugyanakkora,
mint a fenti független ponthalmaz!) Lefogó ponthalmazt alkot
F
Y2 ∪ X3 .
független élhalmaz (párosítás), melynek mérete ugyanaz, mint a fenti lefogó ponthalmaz.
Most az általános esetet vizsgáljuk, azaz nem feltétlenül páros gráfot. Ilyenkor, mint a példában láttuk, nem teljesül a König tétel.
τ -ra,
akkor egyben
α-ra
Vegyük észre, hogy a Gallai tételek miatt, ha találnánk gyors algoritmust
is találnánk, illetve egy gyors algoritmus
ν -re
egyben
ρ-t
is meghatározná. A
helyzet a következ®:
τ ⇔ α: ρ ⇔ ν:
nincs gyors algoritmus, valószín¶leg nem is lesz. van polinomiális algoritmus (Edmonds algoritmus), és van minimax tétel is, csak bonyolultabb a
König tételnél:
Tétel (Berge formula) ν=
min X⊆V (G)
ahol
Cp (X)
a
kapunk, hogy
2.2
|V (G)| − (|Cp (X)| − |X|) , 2
G \ X páratlan elemszámú komponenseinek száma. ( G \ X X csúcsait és a bel®lük induló éleket elhagyjuk G-b®l.)
jelöli azt a gráfot, melyet úgy
Folyamok
Vízhálózat tervezése Egy város vízhálózatát szeretnénk megtervezni. Úgy képzeljük, hogy adott egy forrás, ahol termel®dik a víz; adottak városbeli pontok, amiket csövek kötnek össze; adott egy nyel®, ahova csak befelé mehet víz. Minden cs®nek van egy kapacitása, ami azt mutatja meg, hogy adott id®egység alatt maximum mennyi vizet folyathatunk át rajta anélkül, hogy tönkremenne. A csöveket irányítottnak képzeljük, tehát a víz csak az egyik irányba folyhat rajtuk.
Olyan algoritmust keresünk, mely meghatározza, melyik csövön
mennyi vizet engedjünk át ahhoz, hogy a lehet® legtöbb víz jusson el a forrásból a nyel®be. Hogyan lehet ebb®l matematikailag precíz feladatot csinálni? A cs®hálózatnak egy irányított gráf felel meg, melynek minden élén meg van adva egy nemnegatív valós szám, az illet® él kapacitása.
s illetve t fogja jelölni a forrást illetve a nyel®t, azaz ezek olyan csúcsok
melyekb®l csak kifelé illetve befelé indul él. Formálisan:
~ G = (V, E)
irányított gráf,
s∈V
forrás,
t∈V
nyel®.
~ → R+ c:E 0
kapacitás-függvény.
Most megadjuk azt a függvényt, amit keresünk, azaz amely megmutatja, hol mennyi víz folyjon:
De níció (folyam) ~ → R+ f :E 0 (i) (ii)
folyam, ha
~ f (e) ≤ c(e), ∀e ∈ E P P e v -be mutat f (e) = e v -b®l mutat f (e), ∀v ∈ V \{s, t}
Az els® kritérium annak felel meg, hogy egy csövön nem folyhat több víz, mint a kapacitása (különben eltörik); a második annak, hogy a forrást és a nyel®t leszámítva minden csomópontba annyi víznek kell befolynia, mint amennyi kifolyik (mert máshol nem termel®dik és nem t¶nik el víz).
De níció (folyam nagysága)P P f
nagysága:
e s-b®l
ki
f (e) =
e t-be
be
f (e)
Példa
Az ábrán egy
3
érték¶ folyamot láthatunk.
c
a kapacitás,
f
a folyam.
Most megadunk egy másik paramétert, melynek minimuma egyenl® lehet a maximális folyam értékével (azaz minimax tételt keresünk).
De níció (irányított vágás) S ⊆ V, s ∈ S, t ∈ /S
esetén az S által megatározott irányított vágás : az
S -b®l V \S -be mutató élek halmaza.
Az irányított vágás kapacitása:
e∈
X
c(e)
irányított vágás
A minimax tétel a következ®.
Tétel (Ford-Fulkerson) A maximális folyam nagysága akkora, mint a legkisebb vágás kapacitása.
Ha az eredeti terminológiára gondolunk, akkor könnyen látszik hogy bármely folyam nagysága legfeljebb annyi lehet, mint bármely vágás kapacitása. Egy vágásbeli csöveken ugyanis legfeljebb a vágás kapacitása mennyiség¶ víz tud átfolyni a forrást tartalmazó részb®l a nyel®t tartalmazóba, másrészt minden vízcsepp a forrást tartalmazó részb®l indul és végül a másik oldalra kerül, tehát át kell folyjon a vágásbeli csövek valamelyikén.
Ez persze nem teljesen precíz, de precízzé lehet tenni.
A korábbi minimax tételekhez
hasonlóan a bizonyításhoz most már elég egy példát mutatni amikor egy konkrét folyam nagysága egyenl® egy konkrét vágás kapacitásával. A magyar módszerhez teljesen analóg módon egy algoritmust adunk meg,
f ≡0
mely a kezdetben
folyamot addig növeli, míg nem talál ilyen halmazokat. Miel®tt az algoritmusra
térnénk, néhány példát mutatunk.
Példa Az alábbi ábrán egy újabb csatornarendszer van. Kezdetben nem folyik semerre víz. A forrás megnyitása után viszont lehet állítani a víz irányát. Érdemes végiggondolni, a különböz® irányok megnyitásával hogyan változik a rendszerben a folyam nagysága.
Példa Ezen az ábrán a mohó algoritmus nem m¶ködik.
Ha el®ször csak az egyik ágon folyik víz, mégpedig
2 egység, és középen is két egység folyik, akkor nem lehet a forrásból a másik ágat megnyitni.
Más
stratégiával viszont akár 3 egységnyi víz is átvihet®.
Tegyük fel, hogy találtunk egy utat, amiben az élek irányítása nem számít (lehetnek visszafelé mutató élek is), de minden el®re mutató él nem telített, és a visszafelé mutató éleken van folyam. Lehet javítani az átvitt mennyiségen. Ezen az ábrán a kapacitásokat jelölik a
Algoritmus : 1. lépés:
kezdetben
c
értékek.
f ≡0
s → t irányított utat, f -et mine ∈ út |c(e) − f (e)|-vel.
Találunk olyan növeljük
2. lépés:
Találunk olyan
melyre minden élen
f (e) < c(e).
Ezeken az éleken
s − t utat (ahol lehet szembe is menni), ahol az el®re mutató élekre f (e) < c(e), f (e) > 0 (hogy lehessen csökkenteni). A csökkentés során az el®re f nem mehet c fölé, a visszafelé mutatókon pedig nem mehet f 0 alá.
a visszafelé mutatókra mutató éleken
Vegyük észre, hogy az els® lehet®ség speciális esete a másodiknak!
Hogyan találunk megfelel® s-t utat :
csúcsa, és ha az eredeti gráf 1. ha
f (e) < c(e),
2. ha
f (e) > 0,
e
akkor az
akkor
e-t
Segédgráfot készítünk, ahol szerepel az eredeti gráf összes
irányított élére igaz, hogy
e-t
berajzoljuk és ráírjuk a
c(e) − f (e)
értéket;
berajzoljuk fordított irányban és ráírjuk az
f (e)
értéket.
0 < f (e) < c(e), mindkét s → t utat. H ilyet találunk,
Vegyük észre, hogy a kett® nem zárja ki egymást, tehát az olyan élek, melyekre irányban bekerülnek a segédgráfba.
A segédgráfban keresünk irányított
akkor az útbeli élekre írt értékek minimumával lehet javítani.
Ez jó,
{s-b®l
mert tegyük fel, hogy leállt az algoritmus (nincs a segédgráfban
a segédgráfban elérhet® csúcsok halmaza
vágásban a kifelé mutató éleken
f (e) = c(e),
}.
Ekkor
s ∈ S, t ∈ / S.
s → t
út), akkor
Az eredeti gráfban az
a befelé mutató éleken pedig
f (e) = 0
S
S :=
szerinti
a kapacitás. Ezek
szerint a vágás kapacitása megegyezik a talált folyam értékével.
Baj
van akkor, ha bután m¶ködik az algoritmus, ekkor a futási id® nem polinomiális, hanem sokkal
rosszabb.
Példa Az alábbi ábrán, ha a középs® élen javítok, akkor mindig csak 1-et lehet javítani, ezért az algoritmus sokáig tart,
1010
lépés lesz.
Tétel (Edmonds-Karp tétel) Ha mindig a legrövidebb (segédgráfbeli) úton javítunk, akkor polinomiális az algoritmus, tehát gyors.
Tétel Ha a kapacitások egész számok, akkor van egész érték¶ maximális folyam.
2.3
Menger-tételek
Legyen
G = (V, E), s, t ∈ V
Szeretnénk a lehet® legtöbb diszjunkt
s→t
utat találni. Ez több mindent jelenthet aszerint, hogy
a gráf irányított-e, és hogy éldiszjunkt vagy pontdiszjunkt utakat keresünk. (Persze pontdiszjunkt alatt azt értjük, hogy a kezd®- és a végpont közös, de ezenkívül diszjunktak.)
Tétel (1. Menger tétel) G
irányított.
s → t
Az éldiszjunkt irányított
utak maximális száma megegyezik az összes
s → t
utat
lefogó élek minimális számával.
Tétel (2. Menger tétel) G
irányított, nincs közvetlen
s→t
gyezik az összes
s→t
él. A bels®leg pontdiszjunkt irányított utak maximális száma mege-
utat lefogó pontok ( s és
t
nem használható) minimális számával.
Tétel (3. Menger tétel) G
irányítatlan. Az éldiszjunkt
s−t
utak maximális száma megegyezik az összes
s−t
utat lefogó élek
minimális számával.
Tétel (4. Menger tétel) G
irányítatlan, nincs közvetlen
összes
s−t
s−t
utat lefogó pontok ( s és
él. A bels®leg pontdiszjunkt utak maximális száma megegyezik az
t
nem használható) minimális számával.
Tétel (5. Menger tétel) S ⊆ V, T ⊆ V, S ∩ T = ∅, G irányítatlan. Az S → T teljesen pontdiszjunkt utak maximális száma megegyezik az S és T közti utakat lefogó pontok minimális számával. (Például 8 rabló indul S -b®l T -be. Mennyi rend®r kell az keresztez®désekbe, hogy egy rabló se érjen célba?) Itt a lefogó pontok választhatók
S -b®l
és
T -b®l,
viszont a diszjunktság itt azt jelenti, hogy a végpontok is különböz®k.
A korábbi minimax tételekhez hasonlóan könny¶ meggondolni mind az öt esetben, hogy a maximum kisebb egyenl® a minimumnál. 1. Menger tétel bizonyítása.
Mivel
max ≤ min,
jelöli a lefogó élek minimális számát.
szokás szerint elég mutatni
Legyen minden él kapacitása 1.
k
éldiszjunkt utat, ahol
k
Keressünk maximális folyamot
s-b®l t-be. A Ford-Fulkerson-tétel miatt ennek értéke megegyezik a minimális vágás kapacitásával. Ha az s → t utakat lefogó élek minimális száma k , akkor a minimális kapacitású vágás legalább k kell legyen, hiszen egy vágás élei lefogó élhalmazt alkotnak (ez fordítva nem biztos, hogy igaz). Tehát van k érték¶ folyam (volt: van egész érték¶ folyam). Minden élen 0 vagy 1 folyik, ezért van s → t út, ami olyan élekb®l áll, melyeken folyik víz. Ez lesz az els® út. Csökkentsük a folyamot 1-gyel ezen az úton. Kapunk egy
k − 1 érték¶ folyamot.
Itt újra keresünk az 1-et átenged® élekb®l
mert az el®z® élek már nem szerepelhetnek). Ez a 2. út
s → t utat (ez diszjunkt lesz az el®z®t®l,
...
Ez polinomiális algoritmus.
2. Menger tétel bizonyítása.
Új
G0
Visszavezetjük az el®z®re.
gráfot készítünk: minden
G-beli
pontból (kivéve
ezek egy éllel legyenek összekötve. Ezáltal minden ki bel®le vagy pontosan egy él megy bele. A Ha
G-ben s → t
G0 -re
utat lefog
k
pont
0
⇔ G -ben
alkalmazzuk az 1. Menger tételt, így a
~ = (V, E), max ≤ min. G s és t pontokat) két pontot
G0 -beli
készítünk úgy, hogy
pontra igaz lesz, hogy pontosan egy él megy
G-beli pontdiszjunkt utak G0 -ben éldiszjunktak s → t utat lefog k él. G-re alkalmazódik a 2. Menger tétel.
lesznek.
3. Menger tétel bizonyítása.
G = (V, E)
irányítatlan gráfból készül egy
minden él két éllel lesz helyettesítve, ide-oda irányítva.
G-ben
G0
lefogó élekb®l
irányított gráf úgy, hogy
G0 -ben
lefogó éleket kell
készíteni. (Nem világos, hogy mindig van.)
G0 -ben lefogó élekb®l mindig készíthet® G-ben lefogó élhalmaz. (Ez triviális.) G-ben éldiszjuknt s − t utakból készíthet®k G0 -ben éldiszjunk s → t utak. (Ez is triviális.) G0 -ben éldiszjunkt s → t utakból készíthet®k G-ben éldiszjunkt s − t utak. (Ez nem triviális,
de mindig
igaz. Bizonyítandó!) Akkor lehet baj, ha egy él mindkét irányú verzióját használjuk. Erre megoldást jelent, ha kicserélem a problémás él utáni szakaszokat a két út között, és elhagyhatom az élet. Ezt újra és újra ismételve az élszám
s → t utakat kapunk G0 -ben, melyek G-ben is éldiszjunktak. 0 Ezzel készen vagyunk, mert legyen G-ben k éldiszjunkt út. Ebb®l legyártok G -ben k éldiszjunkt utat. 0 Ebb®l az 1. Menger-tétel legyárt k lefogó élt G -ben és ebb®l kapok k lefogó élt G-ben. Így a maximum csökken, el®bb-utóbb olyan éldiszjunkt
tényleg egyenl® a minimummal, ezért polinomiális az algoritmus.
⇒
Az éldiszjunkt utak maximális száma
4. Menger tétel bizonyítása.
5. Menger tétel bizonyítása.
élek. Nevezzük ezeket
s-nek
G-ben
és
G0 -ben
is megegyezik, egyenl®
k -val.
A 2. Menger-tételb®l következik
Vegyünk két új pontot. Az egyikb®l csak és
t-nek.
Az új gráfban
s−t
S -be, a másikba csak T -b®l mennek
útra nézve a 4. Menger-tételt, kijön az állítás.
Mind az ötre polinomiális algoritmust kaptunk.
Következmény
S = {s, s0 } és T = {t, t0 } között ( s → t és s0 → t0 , vagy s → t0 minden S − T utat lefog. Erre van polinomiális algoritmus
Létezik két (pont)diszjunkt út
⇔
nincs olyan pont, amely
Nincs polinomiális algoritmus arra a problémára, hogy van-e
s → t
és
s0 → t0
és
s0 → t)
pontdiszjunkt út és
valószínüleg nem is lesz, ugyanis ez NP-teljes, ld. a következ® fejezetet.
3
NP-teljesség
Ebben a fejezetben olyan problémákat tárgyalunk, melyekre (ellentétben a minimax tételekben szerepl® mennyiségekkel) nincs és valószínüleg nem is lesz gyors algoritmus. Ezt precízen nem tudjuk bizonyítani, de egy elég jó érvet mutatunk rá: megmutatjuk, hogy ha ezen problémák bármelyikére találnánk gyors algoritmust, akkor egy hatalmas problémaosztály összes problémájára is találnánk. Tehát, ha elfogadjuk, hogy ennek a hatalmas problémaosztálynak minden elemére "csak nincs" gyors algoritmus, akkor ezekre az univerzális (tehát az egész osztályt megoldó) problémákra nem lehet. Emlékeztetünk, hogy a könny¶ problémák az alábbiak:
De níció (P-beli) Egy probléma P-beli, ha van rá polinomiális algoritmus. Még egy problémaosztályt de niálunk.
De níció (NP-beli) Egy probléma NP-beli, ha (i) igen/nem választ vár (ii) ha valaki tudja a megoldást, ami igen, akkor polinomiális id®ben meg tud róla gy®zni.
Példa Van
G-ben
Hamilton-kör (minden csúcson átmen® kör)?
NP-beli, mert ha igen a válasz, akkor, ha valaki megsúgja a Hamilton kört (tehát azt, hogy milyen sorrendben kell venni a csúcsokat ahhoz, hogy így egy kört kapjunk az összes csúcson), akkor polinomiális id®ben ellen®rzöm.
De níció (tanú) A tanú az a polinomiális hosszúságú súgás, amelynek segítségével polinomiális id®ben ellen®rizhet®, hogy tényleg igen a válasz.
Példa G-ben
nincs Hamilton-kör .
Nem feltétlenül NP-beli, hiszen arról, hogy nincs, nem lehet gyorsan meggy®zni valakit. Miel®tt továbbmennénk a példákkal jegyezzük meg, hogy ha egy igen/nem választ váró probléma akkor automatikusan
N P -beli
P -beli,
is, hiszen nem is kell tanú, polinom id®ben ki tudjuk deríteni a választ
(ráadásul itt akkor is, ha nem a válasz).
Példa n
összetett-e?
NP-beli, mert a tanú olyan
a
és
b
ab = n.
egészek, hogy
Példa n
prím-e?
Err®l nem látszik azonnal, hogy NP-beli, hiszen nem nyilvánvaló, mit lehetne súgni, ha igen a válasz, de van ilyen súgás. S®t: néhány éve sikerült bizonyítani, hogy a probléma P-beli.
Példa G
színezhet®-e 23 színnel?
NP-beli, hiszen a tanú maga a színezés.
Példa Legkevesebb hány színnel színezhet®k ki a csúcsok? (Kromatikus szám,
χ(G) = 23)
Nem feltétlenül NP-beli már csak azért sem, mert nem igen/nem választ kér, hanem egy számot, de akkor sem t¶nne NP-belinek, ha azt kérdeznénk, igaz-e, hogy a kromatikus szám 23. Arra ugyanis nincs jó tanú, hogy nem 22 vagy annál kevesebb a kromatikus szám.
Példa G-ben
van-e 123 független pont?
P-beli, mert az összes lehet®ség végignézéséhez
n 123
lehet®séget kell megvizsgálni, ez pedig polinomiális.
Látható tehát, hogy az NP-beli problémák egy hatalmas osztályt alkotnak, rengeteg klasszikus feladat tartozik ide. Némelyikük könny¶: van rá polnomiális algoritmus, de valószín¶tlennek t¶nik, hogy mindegyik könny¶ legyen. Ezért van értelme egy problémát nehéznek gondolni a következ® esetben:
De níció (NP-teljes) Egy probléma NP-teljes, ha minden NP-beli probléma rá visszavezethet® polinomiális id®ben, és ® maga NP-beli. A biztonság kedvéért tisztázzuk, ez mit jelent: az A problémát vissza tudjuk vezetni (polinom id®ben) a B problémára, ha az A problémából kiindulva addig tudjuk alakítani (polinom id®ben) a feladatot, hogy egyszercsak a B probléma speciális esetét kapjuk, azaz, ha lenne gyors algoritmusunk a B problémára, akkor az átalakítás és ez a gyors algoritmus együtt az A problémára is gyors algoritmust adna. Gondoljuk meg, hogy ez azt jelenti, hogy ha valaki (a jöv®ben) talál polinomiális algoritmust egy NPteljes problémára, akkor automatikusan az összes NP-belire is lesz gyors algoritmusunk (és ez az, ami valószín¶tlennek t¶nik). Persze az egésznek csak akkor van értelme, ha tudunk mutatni NP-teljes feladatokat. Ilyeneket fogunk látni a következ® szakaszban. Ezt a fejezetet egy de nícióval és egy megjegyzéssel zárjuk.
De níció (co-NP-beli) Egy probléma co-NP-beli (igen/nem választ vár), ha nem esetén van polinomiális id®ben ellen®rizhet® polinomiális hosszúságú tanú. Például az a probléma, hogy egy szám prím-e könnyen ellen®rizhet®en co-NP-ben van (ugyanazért, amiért a tagadása NP-beli): ha nem a válasz, akkor meg lehet adni azt az a-t és b-t, melynek szorzata a kérdéses szám. A tapasztalat az, hogy ha egy probléma NP-beli és co-NP-beli is, akkor P-beli is, de nem világos, hogy miért és nem is biztos, hogy ez általában igaz. Mindenesetre jó példa erre a már említett prímség ellen®rzése. Sokáig csak az volt ismert, hogy NP-beli és co-NP-beli és, mint már említettük, csak nemrégen derült ki, hogy P-ben van.
3.1
NP teljes feladatok
Az els® NP teljes feladat de niálásához némi el®készítésre van szükség. Boole-függvények
f : {0, 1}n → {0, 1},
általában a 0 jelenti a hamisat, az 1 az igazat.
Példa N csúcsú gráfban van-e Hamilton-kör? x1 , . . . , x(N ) : élek, xi = 1 ⇔ az i. él be 2
Gráf megadása
⇔( xi -knek
f (x1 , . . . , x(N ) ) = 2
van húzva.
0/1 értékeket adunk.
1, ha van Hamilton-kör 0, ha nincs Hamilton-kör
1-változós Boole-függvények: identitás és negáció 2-változós Boole-függvények: pl. konjunkció, diszjunkció Azonosságok: disztributivitás, De-Morgan azonosságok, asszociativitás
De níció (Atom) Atom minden elemi logikai kifejezés.
De níció (Literál) Atom vagy annak tagadása.
De níció (Klóz) Klóz literálok diszjunkciója.
De níció (Konjunktív normálforma, KNF) A konjunktív normálforma klózok konjunkciója.
De níció (Diszjunktív normálforma, DNF) Konjunkciók diszjunkciója.
Lemma Minden Boole-függvény felírható KNF-ben és DNF-ben is. Bizonyítás. Nyilván elég az egyiket bizonyítani, hiszen egy KNF átalakítható DNF-é az azonosságokkal
és viszont. Egy
n-változós
Boole függvénybe
2n
féleképpen lehet
olyan helyettesítéshez, melyre a függvény értéke 1 veszünk egy
0/1 értékeket helyettesíteni. Ha minden n hosszú konjunkciót (minden változó
benne van és akkor van tagadva, ha hamis értéket kap az adott helyettesítésben), majd ezeket vaggyal elválasztva egymás után írjuk, akkor DNF-t kapunk.
De níció (SAT-probléma) Bemenet: KNF Kimenet: van-e legalább egy értékadás, amikor igazzá válik az állítás, azaz akkor igen a válasz, ha a formula nem az azonosan nulla Boole függvényt adja. Könny¶ látni, hogy ez egy NP-beli probléma, hiszen, ha igen a válasz, akkor, ha valaki megsúgja, melyik változó legyen igaz, melyik hamis, akkor már könnyen ellen®rizni tudjuk, tényleg igazzá válik-e így a formula.
Példa x1 ∧ ¬x1 ≡ 0,
de
(x1 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 )
kielégíthet® pl. úgy, hogy ha
x1 = x2 =
igaz.
Tétel (Cook tétele) A SAT-probléma NP-teljes. Ahhoz, hogy ezt bizonyítsuk, precízzé kell tennünk, mit értünk algoritmus alatt. Ezt az utolsó fejezetben fogjuk megtenni. Ebben a fejezetben megmutatjuk, hogy a Cook tételt egyel®re elfogadva, milyen más problémákról látható be (teljesen precíz bizonyítással), hogy szintén NP teljesek. A bizonyítás stratégiája mindig a következ® lemmán fog múlni.
Lemma Ha az A probléma NP-teljes, a B probléma NP-beli, és A visszavezethet® polinom id®ben B-re, akkor B is NP teljes. Bizonyítás. Bármely NP-beli probléma polinom id®ben visszevezethet® A-ra, A pedig B-re, így (poli-
nom+polinom=polinom miatt) a két visszavezetés együtt bármely problémát visszevezet B-re.
De níció (3-SAT probléma) A 3-SAT olyan SAT, ahol minden zárójelben legfeljebb három literál szerepel.
Tétel A 3-SAT probléma NP-teljes.
Lemma (a ∨ ¬b) ∧ (¬a ∨ b) = 1 ⇔ a = b. A tétel bizonyítása.
hogy
Fi -kben
Tetsz®leges
S®t
(a1 ∨ ¬a2 ) ∧ (a2 ∨ ¬a3 ) ∧ · · · ∧ (an ∨ ¬a1 ) = 1 ⇔ ai = aj , ∀i, j .
f (x) = E1 ∧ E2 ∧ . . . -t
g(x) = F1 ∧ F2 ∧ . . . -ra ⇔ g kielégíthet®.
visszavezetünk egy
már csak legfeljebb három literál szerepel és
f
kielégíthet®
úgy,
Példa f (x) = ¬x1 ∨ x2 ∨ ¬x3 ∨ x5 ∨ x6 .
Új változók:
y1 , y2 , y3 , y4 , y5 , y6 .
Az új formula a következ®kb®l fog állni
(és jelekkel elválasztva)
(y1 ∨ x1 ) ∧ (¬y1 ∨ ¬x1 ) (eléri, hogy (y1 = ¬x1 ) teljesüljön olyankor, amikor igaz y2 ∨ ¬y1 ) ∧ (y2 ∨ ¬x2 ) ∧ (¬y2 ∨ y1 ∨ x2 ) (eléri, hogy y2 = y1 ∨ x2 teljesüljön, erre a
kovetkez® módon lehet
rájönni:
(y2 ∨¬(y1 ∨x2 ))∧(¬y2 ∨(y1 ∨x2 )) = (y2 ∨(¬y1 ∧¬x2 ))∧(¬y2 ∨y1 ∨x2 ) = (y2 ∨¬y1 )∧(y2 ∨¬x2 )∧(¬y2 ∨y1 ∨x2 ) y3 = y2 ∨ ¬x3 , . . . , y6 = y5 ∨ x6 = ¬x1 ∨ x2 ∨ ¬x3 ∨ x5 ∨ x6 És hozzá kell ésezni y6 -ot a végén.
Újabb ilyenekkel:
De níció (SAT-3 probléma) A SAT-3 olyan SAT, ahol minden literál legfeljebb három példányban szerepel.
Tétel A SAT-3 NP-teljes. Ezt nem bizonyítjuk, de kés®bb ki fogjuk használni.
Lefogási feladat Bemenet:
A1 , . . . , An ⊆ X, k ∈ N k pont X -b®l, melyek
Kimenet: van-e
lefogják az
Ai -ket,
azaz:
∃X 0 ⊆ X, |X 0 | = k : X 0 ∩ Ai 6= ∅, ∀i
Példa A1 = {1, 2, 3}, A2 = {2, 5, 7}, A3 = {4, 7, 8}, k = 2 k = 1 esetén nem a válasz.
esetén igen a válasz, pl.
{2, 7}
lefogja a halmazokat.
Tétel A lefogási feladat NP-teljes Bizonyítás. A SAT-ot polinomiális id®ben visszavezetjük rá, azaz megadunk egy átalakítást, mely KNF-
ból kiindulva legyárt egy lefogási feladatot, melyre pontosan akkor igaz a válasz, ha a formula kielégíthet®. Legyen f (x) = (x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ) ∧ (x2 ∨ ¬x4 ). Vegyük a következ® lefpgási feladatot: X = {x1 , x2 , x3 , x4 , ¬x1 , ¬x2 , ¬x3 , ¬x4 }. Ai = {xi , ¬xi }, i = 1, 2, 3, 4; A5 = {x1 , ¬x2 , ¬x3 , x4 }, A6 = {x2 , ¬x4 }, végül legyen k = 4. Ekkor a lefogási feladatra pontosan akkor igen a válasz, ha f kielégíthet®: Ha találok egy olyan értékadást, ami kielégíti f -et, akkor úgy kapok 4-elem¶ lefogó ponthalmazt, hogy minden i-re veszem xi -t vagy ¬xi -t aszerint, hogy az értékadásnál xi igaz vagy hamis. Másrészt, ha A1 , A2 , A3 , A4 , A5 , A6 lefogható 4 ponttal, akkor f kielégíthet®. Könny¶ észrevenni ugyanis, hogy ⇒ A1 , A2 , A3 , A4 lefogása kikényszeríti, hogy a 4 lefogó pont automatikusan értéket ad az xi -knek ( xi = 1 ⇔ Ai xi -vel van lefogva és nem ¬xi -vel . . . ). Ez az értékadás jó lesz, kielégíti f -et, mert A5 és A6 is le van fogva.
Megjegyzés. már akkor is NP-teljes, ha
|Ai | ≤ 3, ∀i,
mert 3-SAT visszavezetésével ilyen jön létre.
∀x ∈ X
Megjegyzés. Akkor is az, ha
legfeljebb 4 halmazban szerepel, mert SAT-3 visszavezetésével ilyen
keletkezik.
Tétel Az a probléma, hogy egy
G
gráf 3-színezhet®-e, NP-teljes.
f (x1 , . . . , xn ) = E1 ∧ · · · ∧ En , (Ei : zi ∨ zj ∨ zk vagy zi ∨ zj vagy Ei -ben pontosan 3 változó van, ha mégsem így volna, bevezethet® új változó. Pl. x2 ∨ ¬x3 → (x2 ∨ ¬x3 ∨ y) ∧ (x2 ∨ ¬x3 ∨ ¬y), ahol y az új változó. Ekkor fel kell venni egy új E -t is. Olyan háromszögeket rajzolunk, amiknek egy közös csúcsuk van, ez legyen u. Atöbbi csúcsot xi -kkel és ¬xi -kkel indexeljük. Az i. háromszögben vannak xi -k. Az u-t összekötjük v -vel, ami eddig semleges csúcs volt. Minden Ei -hez további csúcsokat és éleket veszünk hozzá. Bizonyítás. A 3-SAT-ot vezetjük vissza.
zi ).
Feltehet®, hogy
Lemma Rakéta alakú kép. A, B, C, D bet¶k vannak rárajzolva. A, B, C, D ki van színezve valahogy legfeljebb három színnel. Ez kiterjed az egész (+5 csúcs) 3-színezésévé fenti folytatása.
⇐
f
kielégíthet®
⇔G
⇔
A, B, C, D színe nem mindnek ugyanaz.
3-színnel színezhet® (ehhez kellett a rakéta ábrája).
x-ei u színén kívüli színeket elnevezhetjük igaznak és hamisnak. Legyen piros az u, kék az igaz, zöld a hamis. Ez egy értékadást fog megadni, xi igaz, ha kék, és xi hamis, ha zöld. A v is zöld legyen. A rakétában fontos, hogy a v színe is hamis legyen. Ekkor a rakéta három x-e nem mind egyforma szín¶. (Ha a végpontok ( x-ek és v ) egyformák, a közbüls® Képzeljük el, hogy valaki kiszínezte az egész gráfot valamilyen színezéssel. Ekkor a szélmalom
két színnel lesznek kiszínezve, ezért az
csúcsok nem kiszínezhet®k három színnel.
⇒
Az értékadás megad egy színezést az
x-ekre,
a
v
színe legyen a hamis szín,
A lemma miatt a rakéta színezése ezekre kiterjed, tehát
G
u
színe legyen egy 3. szín.
három színnel színezhet®.
Fedési probléma Bemenet:
A1 , . . . , An ⊆ X, k ∈ N k darab Ai , hogy
Kimenet: Van-e
ezek egyesítése az egész
X -et
kiadja?
Tétel A fedési probléma NP-teljes.
Bizonyítás. A lefogási feladat duálisa.
Következmény Legfeljebb négyelem¶ halmazokkal is az. (Mert így a duálisban minden elem legfeljebb négy halmazban szerepel, err®l pedig láttuk, hogy szintén NP-teljes.) Megjegyzés. Legfeljebb kételem¶ halmazokkal már polinomiális.
k -partíciós
feladat : A1 , . . . , An ⊆ X, k. Van-e Ai , . . . , Ai : j Ai = X , és Ai -k diszjunktak? S partíciós feladat : A1 , . . . , An ⊆ X (és nincs k). Van-e néhány diszjunkt, melyekre j Ai = X . 1
k
S
j
j
j
Tétel A
k -partíciós
feladat NP-teljes.
k -fedési problémát legfeljebb négyelem¶ halmazokkal. A1 , . . . , An ⊆ X → A0i , . . . , A0n0 ⊆ X , minden Ai minden részhalmazát is belevesszük. Ebben az új rendszerben létezik partíció ⇔ az eredetiben van fedés. 0 Ha az Ai -kb®l diszjunkt módon fedjük X -et, akkor az eredetiben véve az Ai -ket tartalmazókat, fedést kapunk. Ha Ai -kb®l van fedés, akkor lesz¶kítve néhány Ai -t, diszjunkt fedést kapok. Fontos volt, hogy
Bizonyítás. Visszavezetjük rá a
legfeljebb négyelem¶ halmazok legyenek, különben ugyanis a visszavezetés nem lenne polinom idej¶.
Tétel (A partíciós feladat NP-teljes)
k -partíciós feladatot vezetjük vissza. Adott A1 , . . . , An ⊆ X és k ∈ (N ). Van-e k db, X -et? X helyett X ∪ {y1 , . . . , yk }-t vizsgáljuk, ahol az y -ok olyanok, hogy eddig nem voltak benne X -ben. ∀Ai helyett tekintsük az Ai ∪ {yj } halmazokat (minden halmazból k db lett). Ha az új rendszerben van partíció, akkor az automatikusan k halmazból áll. Ha az új rendszerben van partícionálás ⇔ az eredetiben van k -partícionálás.
Bizonyítás. A
melyek partícionálják
Volt:
a
G
gráf 3-színezhet®-e, NP-teljes probléma.
S®t, a 4, 5, 6-színezhet®ség pláne! (Ez nem biztos, hogy egyb®l látszik.) Viszont a 2-színezhet®ség polinomiális, mert páratlan köröket kell keresni.
k -elem¶
független ponthalmaz létezésé nek a problémája is NP-teljes. G
bemenet:
k
gráf,
kimenet: van-e
k
egész
független pont
Tétel Ez NP-teljes. Bizonyítás. A 3-színezhet®séget vezetjük rá vissza.
G
Adott
csúcsú, akkor
G
0
legyen
3n
csúcsú, Egyszer¶en lerajzoljuk
a lemásolt gráfok megegyez® pontjait összekötjük, így lesz
G0 -ben van n független pont ⇔ G 3-színezhet®. 0 ebben a G gráfban találok n db független pontot,
G0 -t
gráfot. Ha G n G-t egymás mellé háromszor ( G1, G2, G3), és a G-beli éleken kívül még további 3n él.
gráf, melyr®l el szeretnénk dönteni, 3-színezhet®-e. Készítünk bel®le egy
Ekkor Ha
akkor az csak úgy lehet, ha minden eredeti csúcs
három példányából pontosan egy van benne. A színezés legyen: piros - a csúcs csúcs
G2-beli
verziója; zöld - a csúcs
Fordítva: adott egy 3-színezés
G3-ból
G3-beli
G-ben.
Akkor
verziója van benne az
n
csúcs
G0 -ben:
n
G1-beli
verziója; kék - a
független pont között.
a piros a
G1-b®l,
a kék a
G2-b®l,
a zöld a
adódik, és ez jó.
Lefogó ponthalmaz egy gráfban Bemenet:
G
gráf,
Kimenet: van-e
k
k
szám
pont, mely minden élet lefog?
Ez ugyanaz, mint a lefogási feladat a legfeljebb kételem¶ halmazokra (ha a kételem¶ halmaz a gráf éleit tartalmazza, és azért legfeljebb, mert lehet hurokél is).
Tétel Ez is NP-teljes. Bizonyítás. Gallai (1. el®adás): a lefogó pontok minimális száma és a független pontok maximális száma
együtt a gráf csúcsainak számát adja. Ha adnak egy lefogási feladatot, akkor az a kérdés, hogy a lefogó pontok minimális száma
k
alatt van,
vagy sem. Létezik
k
lefogó pont
⇔
létezik
n−k
független pont.
Részletösszeg probléma Bemenet:
a1 , . . . , an , b ∈ (N ) ai1 , . . . , aik : ai1 + · · · + aik = b?
Kimenet: van-e
Tétel Ez is NP-teljes. Bizonyítás. A partíciós feladatot vezetjük vissza rá.
S∗ A1 , . . . , An ⊆ X -et. Van-e Aij = X (diszjunkt lefedés)? Ebb®l csinálunk a1 , . . . , an , b-ket. X =P {0, 1, 2, . . . , n − 1}, és q egy nagyon nagy szám. ai = j∈Ai q j b = 1 + q + q 2 + · · · + q n−1S ∗ b = ai 1 + · · · + ai k ⇔ X = Aij ⇐ triviális (a diszjunkt részhalmazoknak megfeleltetem a q hatványainak összegét) ⇒ b = ai1 + · · · + aik , Pn−1 b = i=0 q i = (q i1 + q i2 + . . . ) + (q j1 + q j2 + . . . ) + . . . i Kell, hogy a jobb oldalon minden q pontosan egyszer szerepeljen. Ha q > m, akkor ez OK, mert a jobb i i+1 oldalon kevesebb, mint m zárójel van, és egy q legfeljebb m-szer szerepel ⇒ nem adhat ki q -et.
Adnak
Linerális egyenl®tlenség-rendszer egészekre Bemenet:
A n × n-es
Kimenet:
x = (x1 , . . . , xn ),
mátrix egészekkel, hogy
Ax ≤ b
b = (b1 , . . . , bn )
egészelem¶ vektor.
koordinátánként (azaz
Pn
j=0
ai,j xj ≤ bi , ∀i).
Tétel Ez is NP-teljes. Bizonyítás. A 3-SAT-ot vezetjük vissza.
f (x) = (x1 ∨ ¬x2 ∨ x3 ) ∧ (x4 ∨ x2 ∨ x5 ) 0 ≤ xi ≤ 1 ⇔ −xi ≤ 0 és xi ≤ 1 x1 + (1 − x2 ) + x3 ≥ 1 x4 + x2 + x5 ≥ 1 −(x1 + (1 − x2 ) + x3 ) ≤ 0 −(x4 + x2 + x5 ) ≤ −1
Tétel Egy gráfban létezik-e Hamilton-kör, NP-teljes probléma. (Nem bizonyítjuk.)
4
Közelít® algoritmsok NP-nehéz feladatokra
De níció (NP-nehéz) Egy feladat NP-nehéz, ha minden NP-beli probléma rá polinomiális id®ben visszavezethet®, de ® maga nem feltétlenül NP-beli (azaz nem is igen/nem választ vár, vagy igen/nem választ vár de az igen válasz esetén sincs jó tanú). Sok NP-teljes feladathoz tartozik természetes módon egy keres® feladat (tehét olyan, ami egy számot, csúcshalmazt, stb. ad, nemcsak igent vagy nemet). Ezek általában NP-nehezek.
Példa Mekkora egy gráfban a legkisebb lefogó ponthalmaz? Ez nem NP-beli, mert hiába súgják meg, hogy mennyi, nem ellen®rizhet®, hogy kevesebb jó-e, de könny¶ látni, hogy az adott méret¶ lefogó ponthalmaz létezése (ami NP-teljes) visszavezethet® rá.
Példa Egy gráfban a kromatikus szám négy? Az, hogy a kromatikus szám három-e, NP-teljes probléma, mert ha megmondjuk a 3-színezést, ellen®rizhet®, és a 2-re könnyen ellen®rizhet® (páros-e a gráf ).
Nem tudjuk viszont megmondani, hogy
a gráf kromatikus száma négy-e, mert nem tudjuk ellen®rizni, hogy 3-mal nem színezhet® ki.
Példa Egy gráfban mekkora a legnagyobb független ponthalmaz? Ez sem NP-beli.
NP-teljes feladatokkal való kapcsolat 1. Van-e 2.
k -pontú
lefogó ponthalmaz?
χ(G) ≤ 4?
3. Van-e
k
méret¶ független ponthalmaz?
Ha az egyikre lenne polinomiális algoritmus, akkor a párjára is volna.
Példa Ha lenne polinomiális algoritmus arra, hogy van-e
k -pontú
független ponthalmaz, akkor arra is volna,
hogy mennyi a maximális méret¶ független ponthalmaz. (Ugyanis úgy futtatom, hogy
3n/4, . . . ,
k = n, k = n/2, k =
felezéses eljárással.)
NP-nehéz problémák közelítése Az derült ki, hogy hiába ekvivalensek az NP-teljesek, mégsem lesznek egyforma hatékony közelít® algoritmusok a kapcsolódó NP-nehéz feladatok megoldására: némelyik jól közelíthet®, mások nem.
Példa (Legkisebb lefogó halmaz közelítése ( τ (G))) 2τ .
Algoritmus, mely Lolyan lefogó ponthalmazt talál, melynek mérete legfeljebb Miel®tt ismertetnénk az algoritmust, egy lemmát bizonyítunk.
Lemma F
maximális párosítás
G-ben ⇒ F
végpontjai lefogó ponthalmazt alkotnak. (Most a maximális azt jelenti,
hogy tovább nem b®víthet®.) Bizonyítás. Ha lenne olyan él, melynek egyik végpontját sem tartalmazzák
závehet® lenne
F
végpontjai, akkor az hoz-
F -hez.
A lemma szerint tehát egy
2|F |
méret¶ lefogó ponthalmazt kaphatunk egy
F
maximális párosításból.
Másrészt bármely lefogó ponthalmaz legalább akkora, mint bármely párosítás. Ezért
τ (G) ≥ |F |,
azaz
2τ (G) ≥ 2|F |. Ezekután már könny¶ megfelel® algoritmust csinálni. Akár vehetünk egy legnagyobb párosítást találó algoritmust, de akár mohó módon is csinálhatjuk (hiszen elég egy tartalmazásra nézve maximális párosítás végpontjait megtalálni): Vegyünk egy élet, ennek végpontjai egy tetsz®leges élet: Amikor ez elakad:
x1 , x2 .
Hagyjuk el ezt a két pontot, és a maradék gráfban vegyünk
(x3 , x4 ) . . .
F
maximális párosítás, az
{x1 , . . . , x2k }
halmaz legfeljebb
2τ (G)
méret¶ lefogó.
Vagy másképp: tetsz®leges legnagyobb párosítási algoritmus (Magyar-módszer).
Megjegyzés. Ennél jobb nem ismert, s®t van tétel, mely szerint
algoritmust adni (ha
1, 0? · τ (G)-re
nem lehet polinomiális
P 6= N P ).
Példa (Az utazóügynök problémája) Mese: A lexikonügynöknek azt mondják, hogy menjen el városokba, és adjon el lexikonokat. szervezze meg az útját?
Minden út id®be és pénzbe kerül.
Hogyan
Bárhonnan bárhova el lehet jutni, és az
lenne a cél, hogy a lehet® legolcsóbb körutazást valósítsa meg. Olyan Hamilton-kört kell keresni, aminek minimális a költsége. Az is lehet, hogy nem Hamilton-kör lesz a legocslóbb, de normális esetekben igen. Vegyünk egy
G = Kn
teljes gráfot, és
c : E → R+ 0
költségeket az éleken. Meg kell adni egy minimális
költség¶ Hamilton-kört.
Állítás Ez egy NP-nehéz feladat. Bizonyítás. A Hamilton-kört visszavezetjük rá.
G = (V, E) n-csúcsú hiányzó éleit, és
gráf. Van-e Hamilton-kör?
c(e) =
(
G-ben van Hamilton-kör
0, ha 1, ha
⇔
e G-nek e G-nek
éle nem éle
c : E → R+ 0
olyan lesz, hogy behúzom a teljes gráfhoz
.
Az új problémában a legolcsóbb Hamilton-kör 0 Ft.
A legolcsóbb Hamilton-kör kétszeresét meg tudjuk mondani, de még sokkal jobban is közelíthet®.
Algoritmus a kétszeres közelítésre, ha c-re teljesül a háromszög-egyenl®tlenség.
(Euklideszi
utazóügynök problémája)
Lemma (Lindström-bejárás) Vegyünk egy tetsz®leges
F
fát, amelyre van olyan körséta, mely minden élen pontosan kétszer megy át.
A körsétában az is megengedett, hogy rögtön visszaforduljak egy pontból. A lemma bizonyítása.
(Euler-tétel: ha minden csúcs páros fokú, akkor van benne körséta.)
Minden élet helyettesítünk egy ide-oda éllel (két él, ami két irányba mutat). Automatikusan irányított gráfot kapunk, melyben minden pontra a bemen®k fokszáma megegyezik a kimen®k fokszámával. Így van irányított Euler-körséta. Az eredeti gráfban így minden élen kétszer megyünk végig.
Lemma Ha c-re teljesül a háromszög-egyenl®tlenség, akkor egy hosszabb út költsége is nagyobb, mint egy közvetlené. (Olcsóbb közvetlenül menni valahova, mint több városon keresztül.) Algoritmus. Vegyünk egy minimális költség¶
x1 → x2 → · · · → x2n−1 = x1
ennek
F
feszít®fát. (Erre van polinomiális algoritmus.) Legyen
egy Lindström-bejárása. (A csúcsok halmaza
minden élen kétszer mentünk végig. Azért
2n − 1,
mert egy fának
n−1
V = {x1 , . . . , xn },
és
éle van, a vége ugyanaz, mint az
eleje, és mindegyiken kétszer megy végig.) Vegyük észre, hogy 1.
F
költsége legfeljebb annyi, mint az optimális Hamilton-kör költsége, mert Hamilton-kör
feszít®fa. Ennél
F
−1
él is
olcsóbb, mert ® meg minimális költség¶.
2. A Lindström-bejárás költsége pedig pontosan kétszerese az
F
költségének, mert minden élet kétszer
járt be. 3. A Lindström-bejárásból legyártunk egy Hamilton-kört, ami legfeljebb annyiba kerül, mint a Lindströmbejárás. A Hamilton-kört úgy kapjuk, hogy a bejárásban kihagyjuk az ismétl®d® csúcsokat. Ez nem lehet drágább, mert
xi → xi+1 → xj
helyett
xi → xj -t
véve a 2. lemma szerint olcsóbban ússzuk meg.
Hátizsák-feladat Van a hátizsáknak teherbírása, és a cél az, hogy a hazavitt dolgok értéke a lehet® legnagyobb legyen.
Ibara-Kim algoritmus : rögzített
5
ε
ez minden
ε-ra csinál olyat, mely legalább (1 − ε) optimálisat bepakol.
Minden
esetén polinomiális.
Turing-gép
A számítógép - Turing-gép. Kell egy ábécé: Van
k
Σ
véges halmaz, tegyük fel, hogy
∗, 0, 1 ∈ Σ.
db szalag, mindegyik szalag mindkét irányban végtelen.
Minden szalagon van író-olvasó fej. Kezdetben minden fej a kezd®mez®n áll. Kezdetben mindenhová
∗ van írva, kivéve a szalagon a kezd®mez®t®l jobbra, ahol lehet egy véges hosszúságú
bitsorozat (vagy szó az ábécé bet¶ivel). Van vezérl®egység, aminek vannak állapotai.
Γ
véges állapothalmaz.
ST ART, ST OP ∈ Γ
Mindig valamilyen állapotban van a gép. Minden pillanatban megnézi, hogy melyik fej mit lát.
k
db
Σ-beli
bet¶t olvas.
Megnézi, hogy milyen
állapotban van a vezérl®egység. Ekkor: minden fej átírhatja, amit lát és léphet egyet balra vagy jobbra, vagy maradhat helyben.
Új
állapotba mehet át.
De níció (Turing-gép) A Turing-gép < k, Σ, Γ, α, β, γ >, ahol k ≥ 1 egész szám; Σ véges halmaz, ∗, 0, 1 ∈ Σ ábécé; Γ véges halmaz, ST ART, ST OP ∈ Γ állapothalmaz; α : Σk × Γ → Γ azt mondja meg, melyik állapotba megy át; β : Σk × Γ → Σk azt mondja meg, mit írnak a fejek; γ : Σk × Γ → {−1, 0, 1}k azt mondja meg, ki merre lép. ∗ nem része a bemenetnek. Bemenet: az a k szó, ami az induláskor a szalagokra van írva. Kimenet: azok a szavak, amik a m¶ködés végén a szalagokon olvashatók. Jelölés:
h(i):
mi van az
i.
szalagra írva.
Feladatok 1.
Adott egy szó, fordítsuk meg. Megoldás: Legyen kétszalagos Turing-gép, az els® szalagon a bemenet végére állok, majd átmásolom
a másik szalagra visszafelé léptetve. Azért megyünk az els® végére, hogy a kimenet a második szalag kezd®pozíciójánál kezd®djön.
Γ = {ST ART, ST OP, IRAS} h(1) 6= ∗, akkor 1. fej jobbra lép h(1) = ∗, akkor 1. fej balra lép, IRAS
Három állapot lesz:
ST ART : ( IRAS :
ST OP : 2.
(
ha ha
ha ha
h(1) = ∗, h(1) 6= ∗,
akkor akkor
ST OP állapotba lép 2. fej h(1)-et ír, 2. fej →
állapotba lép
lép, 1. fej
←
lép
nem csinál semmit
Mit csinál a Turing-gép?
Γ = {ST ART, ST OP } k=3 ha h(1) = h(2) 6= ∗, ST ART : ha h(1) = h(2) = ∗,
akkor 1., 2. fej jobbra lép akkor 3. fej 1-et ír és
minden más esetben 3. fej 0-t ír és
ST OP
ST OP
3.
Készíts Turing-gépet, amelyik a bemenetet megduplázza!
4.
A bemenetr®l eldönti, hogy tükörszó-e. 0-t ír, ha nem palindroma, 1-et ír, ha az. (Visszafelé ugyanaz, vagy nem ugyanaz?)
5.
Ha a bemenet
n
db 1-es, akkor a kimenet legyen
2n
db 1-es.
De níció T1 =< k, Σ1 , Γ1 , α1 , β1 , γ1 >, T2 =< k + 1, Σ2 , Γ2 , α2 , β2 , γ2 > és Σ1 ⊆ Σ2 . T2 a p programmal szimulálja T1 -et, ha pΣ2 -beli szó és bármely (x1 , . . . , xk ) (xl : Σ1 -beli szó) bemenetre T2 -nek (x1 , . . . , xk , p)-t adva T2 ugyanazt csinálja, mint T1 . (Akkor és csak akkor áll meg véges id®n belül, ha T1 megáll ((x1 , . . . , xk ) bemenettel) és T2 els® k szalagjára megálláskor ugyanaz lesz írva, mint T1 els® k szalagjára.)
De níció T =< k + 1, Σ, Γ, α, β, γ > k + 1 szalagos Turing-gép univerzális a k -szalagos Turing-gépekre 0 0 minden T k -szalagoshoz van olyan p program, hogy T szimulálja T -t a p programmal.
nézve, ha
Tétel A Turing-gép programozható.
6
...
Lemma Feltehet®, hogy a bemenet az 1.
szalag kivételével üres (csupa
∗
van rajta), és a kimenet a
k.
szalag
kivételével üres. Bizonyítás. Sok szalag helyett lehet egy szalag, a sok szalag tartalma egy szalagon lesz sorban, és két
adatsort új jel fog elválasztani. A m¶ködés el®tt a a többi szalagra, így lesz
k
T
gép átmásolja a 2. adatsortól kezdve az adatsorokat
szalag.
Tétel Minden
k szalagos Turing-géphez létezik k+1 szalagos univerzális Turing-gép, ami szimulálja a m¶ködését.
Bizonyítás. El®ször
A
k + 1.
k+2
szalaggal:
szalagon a szimulálandó gép m¶ködése lesz, a
k + 2.
szalagon az lesz, hogy milyen állapotban
van a szimulálandó gép.
T 0 =< k, Σ, Γ, α, β, γ >. Γ ↔ r hosszú szavak Σ-ból, kivéve ST OP , mert neki nem lesz megfelel®je. k + 1. szalag: egy g állapot, utána h1 , . . . , hk jelek, ami r hosszúságú, majd felírjuk β(h1 , . . . , hk , g)-t, ami r hosszú, α(h1 , . . . , hk , g)-t, ami k hosszú, γ(h1 , . . . , hk , g)-t, ami k hosszú. Ez az egész legyen összesen l hosszúságú. Az összes létez® (h1 , . . . , hk , g)-re egy-egy ilyet kell írni egymás után.
Szimulálandó gép:
Az összes szituáció egy szalagon lesz, vagyis a szimulálandó Turing-gép egy szalagon lesz leírva.
A
k + 2.
r
szalag:
hosszú szóval lesz kódolva a
A T Turing-gép m¶ködése : Szimuláljunk egy
k
ST ART
állapot.
szalagos Turing-gépet. Mit csináljon az én Turing-gépem?
Ez itt nem volt teljesen pontos (pontosabban lásd a Lovász jegyzetet!).
Más a sorend, mint a fenti
leírásnál, azaz el®bb az állapotot kellene megnézni, és utána azt, hogy vajon mi van az els®
k
szalag feje
alatt.
k
Megnézi, hogy hol van az els® van-e, mint amit a
k
fej. Megnézi, hogy vajon a
k + 1.
szalag elején nem pont az a
k
bet¶
fej lát. Ha abban lenne, akkor lehetne menni az új állapotba (meg kell nézni, hogy
új állapotba kell-e menni).
β
szerint az új állapot kódjával felülírja a
γ
szerint beírja a fejekre az új adatokat.
k
szerint mozgatja a
ST ART
állapot kódját, majd
α
fejet megfelel®en.
k
Mi a helyzet akkor, ha nem az a kód van a szalag elején, mint amit a
fej lát? Ilyenkor elmozgatja a fejet
a következ® blokk elejére, és újra összehasonlítja ott. Amíg nem találja meg az állapotot, addig megy jobbra egy blokkot.
ST OP
állapotba kerül a szimulálandó gép, ha eljut az üres blokkig.
Hogyan szabadulunk meg a
k + 2.
szalagtól? A
k + 1.
szalagon a kezd®helyt®l balra teszem a
k + 2.
szalag tartalmát, majd a jelek közé 0-t, vagy 1-et írok. Akkor van 0, ha nincs ott a fej, akkor van 1, ha ott van a fej. Összesen két egyes van tehát, ezt a két pozíciót a gép meg tudja jegyezni, és akkor tudja, hogy mi az a két hely, amit olvasni kell. Lépéskor az 1-est teszi át egy pozícióval jobbra vagy balra.
. . . , 0/1, h02 , 0/1, h01 , 0/1, h1 , 0/1, h2 , 0/1, . . .
Tétel Bármely
k+1
szalagos Turing-gép helyettesíthet®
k
szalagossal (mégpedig olyannal, aminek csak az els®
szalagjára van írva valami a m¶ködés elején és végén).
k . és a k + 1. szalag helyett veszek pontosan egy szalagot, mint az el®bb, a kezd®állapottól k + 1. szalag tartalma, és a fejeket megint 0 vagy 1 jelöli. Ismét összesen két 1-es van. Az
Bizonyítás. A
balra lesz a
el®z®höz képest az a különbség, hogy most nem tudom, mennyi a ráírt adat pontosan. (Az univerzálisnál tudtuk, hogy milyen hosszú az adat.) Tehát ez a bizonyítás így még nem jó. Ehelyett az kell, hogy, ha
y -ok, a másikon . . . , x1 , 0/1, y1 , 0/1, x2 , 0/1, y2 , 0/1, . . . az egyik szalagon vannak az
az
x-ek,
akkor helyettük legyen a következ®:
Az aktuális helyzetet modulo 4 vizsgálva kiderül, hogy mit is kell csinálni.
Ha
mod(4) = 1,
akkor az
egyik szalag adata, ha 2, akkor 0/1, ha 3, akkor a másik szalag adata, ha 0, akkor 0/1.
Következmény Ha a
cN
k+1
szalagos
N -et
lép, akkor a
k
szalagos legfeljebb
O(N 2 )
lépést tesz. Minden lépésb®l legfeljebb
lépés lesz ( c konstans).
Megjegyzés. Elég a Megjegyzés.
k
k=1
szalag
⇒
esetet nézni. 1 szalag esetén a lépésszám
k−1
N → O(N 2
).
Ez polinomiális lépésszámból
polinomiálisat készít. Megjegyzés. Bizonyítható, hogy a Megjegyzés. Univerzális
k+1
k⇒1
esetén
N → O(N 2 )
a lépésszám.
szalagosnál, ha a szimulálandó
k
szalagos
N -et
lép, akkor a szimulátor
O(N )-et.
Tétel k -ra létezik egyszalagos univerzális O(N 2 )-et lép. (A konstans függ k -tól.)
Minden
7
k
szalagosokra nézve, mely
N
lépés helyett
...
Church tézis : Σ
Turing-gép a
algoritmus az, ami Turing-géppel megoldható.
véges halmaz, ez lesz az ábécé.
∗:az
üres jel.
Σ0 = Σ\{∗}. Σ∗0 := Σ0 -ból
alkotható véges hosszúságú
szavak.
De níció (rekurzív függvény) f : Σ∗0 → Σ∗0
rekurzív (kiszámítható), ha létezik Turing-gép, melynek 1. szalagjára
belül megáll és utolsó szalagjára
f (x)
van írva.
x-et
írva véges id®n
De níció (nyelv) L ⊆ Σ∗0
nyelv.
De níció (rekurzív nyelv) L
rekurzív nyelv, ha a karakterisztikus függvénye (
x-et
Azaz van olyan Turing-gép, hogy az els® szalagra
x∈L
0-t, vagy 1-et ír aszerint, hogy
vagy
χL )
χL (x) =
rekurzív, azaz
(
1, 0,
x∈L x∈ /L
ha ha
rekurzív.
írva véges id®n belül megáll és az utolsó szalagra
x∈ / L.
Következmény L
rekurzív
⇔L
rekurzív ( L komplementere).
Következmény Van nem rekurzív nyelv. Ugyanis a nyelvek száma kontinuum, de a Turing-gépek száma megszámlálható.
De níció (rekurzíve felsoroható nyelv) L nyelv rekurzíve felsorolható,
L = {} vagy ∃f : Σ∗0 → Σ∗0
ha
rekurzív függvény, melynek értékkészlete
L.
Állítás A következ® kijelentések ekvivalensek: (i) Egy
L
nyelv rekurzíve felsorolható
(ii) Létezik
T
(iii) Létezik
T
Bizonyítás.
Turing-gép, hogy els® szalagjára
x-et
írva
T
megáll véges sok lépés után
⇔ x ∈ L.
Turing-gép, mely esetleg végtelen sokáig m¶ködik, de felsorolja (akár ismétléssel)
(i) → (iii):
Létezik
T
Turing-gép, hogy
T
=L
kimenete
szavai. Csinálunk egy
L szavait. T0
Turing-
gépet, mely két dolgot tud:
1. felsorolja 2.
Σ∗0
∀x ∈ Σ∗0 -ra
(iii) → (i): T
elemeit,
lefuttatja
T -t
az
x
bemenettel, majd kiírja, ami
Turing-gép felsorolja
a pozitív egész számok.
n ∈ (N )
L
T
kiírna.
szavait. Ehhez készítek egy
esetén
0
T n
lépésig m¶ködteti
T0
T -t,
Turing-gépet, melyre a bemenetek majd kiírja a
T
által utoljára kiírt
szót. (Ezáltal végessé tehet® a futtatás. Gond, hogy nem tudjuk, kijön-e egy adott szó. Pl. nem tudjuk eldönteni, hogy angolul van-e egy szó.)
(ii) → (iii): T Turing-gép akkor és csak akkor T 0 -t készítünk. x1 , x2 , x3 , · · · ∈ Σ∗0 , és ezeket a
áll le véges id®n belül, ha a beadott
x L-beli.
Ebb®l
szavakat párba állítom a pozitív egész számokkal.
(A
természetes számok és a racionális számok bijekciójánál látott átlós felsorolásban sorolja fel ezeket a párokat. Egy pár azt jelenti, hogy a gép az adott bemenetre hány percig m¶ködjön.)
T0
ilyen sorrendben
(N ) × Σ∗0 párokat. Ha az
(n, x) ∈ (n, x)-hez ér, akkor T -t m¶ködteti x bemenettel n lépésig. Ha ezalatt T leáll, akkor kiírja x-et. (iii) → (ii): Könny¶. T felsorolja L-et, készítsünk T 0 -t, ami olyan, hogy x bemenet esetén m¶ködteti T -t. Ha észreveszi, hogy T kiírta x-et, akkor leállítja T -t és megáll. veszi az
Állítás 1. Ha
L
rekurzív, akkor rekurzíve felsorolható.
2. Ha
L
rekurzív
Bizonyítás. 1.
⇔ L, L
rekurzíve felsorolható.
Felsorolom
Σ∗0
elemeit, majd mindre lefuttatom
kinyomtatom az elemet, ha 0-t, akkor nem. Ez felsorolja
L
T -t (L-et
eldönt® gép); ha
T
1-est ír,
szavait.
⇒:igaz, volt. ⇐: T1 felsorolja L-et, T2 L-et. Készítek T 0 -t, ami m¶ködteti T1 -et és T2 -t, amíg valahol meg beírt x szót. Ekkor mindent leállít és aszerint ír 0-t vagy 1-et, hogy melyik gépen látta meg. 2.
Adjunk példát egy nem algoritmizálható problémára
nem látja a
Tétel T -re: LT = {x : T x 1.
LT
2.
T
bemenettel véges id®n belül megáll }
rekurzíve felsorolható.
univerzális
⇒ LT
nem rekurzív.
Bizonyítás. 1. volt: rekurzíve felsorolható
ha a szó
⇔
létezik
T 0,
ami akkor és csak akkor áll le véges id®n belül,
LT -beli.
2. Nehéz, trükkös diagonális módszerrel bizonyít (az egész számok nincsenek annyian, mint a részhal-
LT is rekurzíve felsorolható. Ekkor létezik x ∈ LT . Legyen T kétzalagos Turing-gép, 0 ami az egyszalagosakra nézve univerzális, és legyen T egyszalagos. Legyen p az a program, mellyel T 0 szimulálja T -t. Megáll-e véges id®n belül T a következ® bemenettel: mindkét szalagjára p-t írom? 0 Ha a p bemenet benne van L-ben, így nincs benne a komplementerében, akkor T végtelen sokáig fut, ezért T -nek is végtelen sokáig kellene m¶ködnie, pedig már leállt. 0 Ha a p nincs benne L-ben, akkor T nem áll le, de p benne van a komplementer-nyelvben, ezért T leáll, 0 de T T -t szimulálja, vagyis le kéne állnia. Sehogy sem szimulálja jól, ha p a bemenet. Ellentmondásra jutottunk. mazai). Indirekt tegyük fel, hogy nem igaz az állítás. Ekkor
T 0,
olyan
amely akkor és csak akkor áll le véges id®n belül, ha
Állítás (Algoritmikusan eldönthetetlen problémák) Bemenet
1. x 2. T 3. T
Kimenet megáll-e
Turing-gép leírása
van-e bármilyen bemenet, amire leáll véges id®n belül?
LT
nem rekurzív.)
Tegyük fel, hogy van ilyen algoritmus.
Legyen mint
x
T.
bemenetre? ( T rögzített univerzális Turing-gép.)
megáll-e üres bemenettel?
Bizonyítás. 1. Világos. (
2.
T x
Turing-gép leírása
bemenethez
T0
Ebben az esetben az 1.
Turing-gép olyan, ami az elején
x-et
is menne, ami viszont nem megy.
ír az els® szalagra, majd úgy m¶ködik,
Az egyik pontosan akkor áll meg, amikor a másik, tehát ekvivalens a két probléma.
3. Tegyük fel, hogy van ilyen, ekkor a 2. is menne. Egy adott
T.
a bemenetet, majd úgy m¶ködik, mint
Ekkor
T
0
T -hez
készítek
T 0 -t,
mely az elején letörli
leáll legalább egy bemenetre
⇔ T
leáll az üres
bemenetre.
Tétel Nem létezik algoritmus a következ®re: Bemenet: dominókészlet. Kimenet:kirakható-e a sík ezzel a dominókészlettel.
Bizonyítás vázlat.
Bebizonyítjuk, hogy ha lenne erre algoritmus, akkor az el®z® 2.
pontjára is volna.
Vegyünk egy végtelen sokáig m¶köd® Turing-gépet, aminek az állapotai a dominók helyzetei. Rájövünk, hogy a dominókból végtelen sok van, és ellentmondás lesz. (Ez vizsgán nem kell.)
8
...
De níció (Polinomiális Turing-gép) T
Turing-gép polinomiális, ha
∃c1 , c2 ∈ (N )
és egy
n
hosszú bemenet, amire
T ≤ c1 · nc2
lépést tesz.
De níció (Polinomiális nyelv) L
nyelv polinomiális (jel: L
bemenetre
c1 · |x|c2
∈ P , L P -beli), ha van polinomiális T x ∈ L vagy x ∈ / L.)
Turing-gép, mely eldönti
L-et. (x
id®n belül kiírja, hogy
De níció (Nemdeterminisztikus Turing-gép) < k, Σ, Γ, Φ >, ahol k Φ ⊆ (Σk × Γ) × (Σk × Γ × {−1, 0, 1}k ) reláció.
Minden pillanatban többféle dolgot is tehet: állapothalmaz,
k k
Σ :
z
db
−1, 0, 1
}|
{
((h1 , . . . , hk , g), h01 , . . . , h0k , g 0 , −1, 0, 0, 1, . . .).
a szalagok száma,
Σ
az ábécé,
Γ
az
De níció T
nemdeterminisztikus Turing-gép felismeri az
számolás (amit a
Φ
L nyelvet,
ha
x ∈ L ⇔ x bemenet esetén van olyan legális x ∈ L-re lehetnek
megenged), mely véges id®n belül leáll, és a gép egy 1-est ír ki. (
olyan m¶ködések is, melyek leállnak és 0-t írnak ki, és olyanok is, melyek sose állnak le, csak az a fontos, hogy legyen olyan m¶ködés is, melynek végén 1-est ír ki. Tilos
x∈ / L-re
leállni és 1-est kiírni.)
Tétel L
felismerhet® egy
T
nemdeterminisztikus Turing-géppel
⇔L
rekurzíve felsorolható.
⇒: T m¶ködését kódoljuk. (h1 , . . . , hk , ST ART ) | {z } 0 0 0 kezd®állapot (h1 , . . . , hk , g, ε1 , . . . , εk )(h00 ,...,h00 k ,g,ε1 ,...,εk )... | {z } 1
Bizonyítás.
εi ∈{−1,0,1}
T0
Egy ilyen véges szó = egy véges hosszú m¶ködés kódja. Van olyan
egy ilyen szóról megállapítja, hogy
L0
T
determinisztikus Turing-gép, mely
egy legális számolását kódolja-e.
legyen az a nyelv, amiben azok a szavak vannak, melyek
T
egy legális számolását kódolják.
T 0 L0 -t
ismeri fel.
T0
Módosítható
kódolja-e, hogy
T 0 -t
úgy, hogy a szó elején még egy
T x
x
bemenet is legyen, és azt nézze meg, hogy a szó azt
bemenet esetén véges ideig legálisan m¶ködik és végül elfogadja
úgy módosítjuk, hogy sorravegye az összes véges szót, megnézze, hogy ez egy (
számolás, elfogadás) hármas kódja-e, ha igen, kiírja
⇐: L
x-et. x bemenet,
legális
x-et.
⇒ létezik T determinisztikus Turing-gép, mely akkor és csak akkor áll le x bemenetre, ha x L-beli szó. Módosítjuk úgy, hogy ha leáll, akkor írjon ki egy 1-est.
rekurzíve felsorolható
véges id®n belül egy
De níció (NP-beli nyelv) L
NP-beli ( L
∈ N P ),
ha van olyan nemdeterminisztikus
olyan legális számolása
T -nek,
mely
c1 · |x|c2
T
x ∈ L ⇔ x bemenettel van x-et. Ha x ∈ / L, akkor bármi
Turing-gép, hogy
id®n belül leáll és elfogadja
történhet, csak az nem, hogy véges id®n belül leáll és 1-est ír ki.
De níció Az
L1
nyelv polinomiális tanúja az
L2
nyelvnek, ha
x ∈ L2 ⇔ ∃y : x&y ∈ L1 , |y| ≤ c1 · |x|c2 ∧ L1 ∈ P . y
a tanú.
Tétel L ∈ NP ⇔
van hozzá polinomiális tanú.
⇒ Van egy T nemdeterminisztikus Turing-gép, mely L-et polinomiális id®ben felismeri. Az L1 = x&y , ahol y T egy polinomiális idej¶ legális m¶ködése, mely x-et fogadja el. Ez jó tanú. ⇐ L-hez tanúnyelv L0 . Kéne T nemdeterminisztikus Turing-gép, mely L-et polinomiális id®ben felismeri. L0 polinomiális, azaz van T 0 determinisztikus Turing-gép, mely L0 -t polinomiális id®ben felismeri. Legyen x-re |y| ≤ c1 · |x|c2 , és T lépéseinek a száma c1 · |x|c2 . Bizonyítás.
T m¶ködése: 1.
Kiszámítja
c1 · |x|c2 -et.
(Az esetleges tanú maximum ilyen hosszú lehet.) Ennyi 1-est ír egy külön
szalagra. 2.
A bementre
3.
≤ 1-esek
4.
Átmegy
x
után egy
&
jelet ír.
száma darab bet¶t ír az
T 0 -be
x&
után, ez lesz az
y.
(Az 1-esek száma az 1. lépést®l függ!)
és polinomiális id®ben ellen®rzi, hogy a kapott
x&y ∈ L0 -e.
De níció (Visszavezetés) L1
nyelv polinomiális id®ben visszavezethet®
L2
f : Σ∗1 → Σ∗2 függvény, x ∈ L1 ⇔ f (x) ∈ L2 .
nyelvre, ha van olyan
polinomiális id®ben számolható (determinisztikus Turing-géppel) és
De níció (NP-teljes nyelv) NP-teljes, ha minden NP-beli nyelv rá polinomiális id®ben visszavezethet®.
Tétel (Cook-tétel) A SAT nyelv NP-teljes.
Ha igen, 1-est ír ki.
mely
L NP-beli nyelv, azaz van hozzá T egyszalagos nemdeterminisztikus Turing-gép, melyre ∀x ∈ L-re ∃c1 · |x|c2 hosszú számolás, mely elfogadja x-et. Adott a T és egy x bemenet, ebb®l kell készíteni kimenetként f (x1 , . . . , xM )-et, mely akkor és csak akkor c kielégíthet®, ha T c1 · |x| 2 lépésben elfogadja x-et. Bizonyítás.
Kódolni fogjuk a függvényben a m¶ködést:
N := c1 · |x|c2 f változói: 1.
x(n, g),
ahol
1 ≤ n ≤ N, g ∈ Γ
2.
y(n, p),
ahol
0 ≤ n ≤ N, −N ≤ p ≤ N
3.
z(n, p, h),
ahol
(igaz az értéke, ha az
n.
pillanatban
(igaz az értéke, ha az
0 ≤ n ≤ N, −N ≤ p ≤ N, h ∈ Σ
n.
g
állapotban van a gép);
pillanatban a fej a
(igaz az értéke, ha az
n.
p.
mez®n van);
pillanatban a
p.
mez®n
h
jel van).
f
a változói konjunkciója. Egyszerre
≥ 1
állapotban van a gép:
legalább egy állapot igaz.
≤ 1 állapotban van a gép: [baj, x(n, g )] ¬x(n, g) ∨ ¬(n, g 0 )∀n, g 6= g 0 -re. Egyszerre
W
g∈Γ
x(n, g)∀n-re.
ha az
n.
Ez úgy lesz igaz, ha minden pillanatban
pillanatban
g -ben
és
g 0 -ben
0
is van a gép:
x(n, g) ∧
Így a gép pontosan egy állapotban van. A fej egy adott pillanatban egy helyen van:
∀n :
W
−N ≤p≤N
y(n, p), ¬y(n, p) ∨ ¬y(n, p0 )∀p 6= p0
esetén.
Minden pillanatban a szalag egy mez®jére egy jel van írva:
z(n, p, h), ¬z(n, p, h) ∨ ¬z(n, p, h0 )∀h 6= h0 esetén. x = h1 , . . . , hn (−N és N között 0-tól van írva x, el®tte és utána ∗-ok vannak.) z(0, −N, ∗) ∧ z(0, −N + 1, ∗) ∧ · · · ∧ z(0, −1, ∗) ∧ z(0, 0, h1 ) ∧ z(0, 1, h2 ) ∧ · · · ∧ z(0, N, ∗) ST ART, ST OP : x(0, ST ART ) ∧ x(N, ST OP ) végén 1: y(N, 0, 1) 0 0 0 0 0 A fej csak oda ír, ahol van. [Baj: y(n, p) ∧ z(n, p , h) ∧ z(n + 1, p , h ), ∀n, p 6= p , h 6= h , kell: ¬y(n, p) ∨ 0 0 0 ¬z(n, p , h) ∨ ¬z(n + 1, p , h ) feltétel megtiltja a fenti eset el®fordulását. Ha ezt ∀n, p 6= p0 , h 6= h0 -re ∀n, p :
W
h∈Σ
Bemenet:
megcsinálom, akkor elérem, hogy egy id®ben egy bet¶ csak egy helyen legyen.]
Φ ⊆ (Σ × Γ) × (Σ, Γ, {−1, 0, 1}) x(n, g) ∧ y(n, p) ∧ z(n, p, h) ∧ x(n + 1, g 0 ) ∧ y(n + 1, p + ε) ∧ z(n + 1, p, h0 ) akkor, 0 0 ∀((h, g), h , g , ε) ∈ / Φ (Φ megmondja, hogy milyen állapotból milyenbe menjen, de itt azokat
A gép m¶ködése:
Baj: ha képes arra, hogy amikor
sz¶rjük ki, amiket ® nem csinálhat jogosan. Szabálytalan lépéseket kell keresni.) Ezért azt kell tenni, hogy
¬x(n, g) ∨ ¬y(n, p) ∨ ¬z(n, p, h) ∨ ¬x(n + 1, g 0 ) ∨ ¬y(n + 1, p + ε) ∨ ∧z(n + 1, p, h0 )
