Bonyolults´agelm´elet
Monday 10th October, 2016, 17:44
Bonyolults´ agelm´ elet
NP-teljes gr´afelm´eleti probl´em´ak
T´etel ´ probl´ema NP-teljes. A Hamilton-Ut
Bonyolults´ agelm´ elet
NP-teljes gr´afelm´eleti probl´em´ak
T´etel ´ probl´ema NP-teljes. A Hamilton-Ut ¨ Otlet ´ ekv´alaszt´o” gadget: ,,Ert´
Bonyolults´ agelm´ elet
NP-teljes gr´afelm´eleti probl´em´ak
T´etel ´ probl´ema NP-teljes. A Hamilton-Ut ¨ Otlet ´ ekv´alaszt´o” gadget: ,,Ert´
Bonyolults´ agelm´ elet
NP-teljes gr´afelm´eleti probl´em´ak
T´etel ´ probl´ema NP-teljes. A Hamilton-Ut ¨ Otlet ´ ekv´alaszt´o” gadget: ,,Ert´
(Balr´ol jobbra ha megy egy Hamilton-´ ut, akkor v´alasztanunk kell a ,,fenti” ´es a ,,lenti” u ´tvonal k¨ oz¨ ul egyet.) ⇒ mint egy ´ert´ekad´as – ilyen gadgetb˝ ol v´altoz´ onk´ent lesz egy
Bonyolults´ agelm´ elet
¨ Otlet ,,XOR” gadget:
Minden Hamilton-´ ut egy olyan gr´afban, ami ezt a gadgetot fesz´ıtett r´eszgr´afk´ent tartalmazza, a k¨ ovetkez˝ ok egyike ezen a gr´afon bel¨ ul:
Hogy ´atl´athat´obb legyen a rajzunk, ezt a gadgetet ´ıgy rajzoljuk: + Bonyolults´ agelm´ elet
¨ Otlet A XOR gadgettel egy gr´afban olyan Hamilton-k¨ ort keres¨ unk, melyben ki tudjuk k¨otni bizonyos ´elp´arokra, hogy a k´et ´el k¨oz¨ ul a keresett Hamilton-k¨or pontosan egyen haladjon ´at. ´ visszavezet´eshez: A teljes konstrukci´o a 3Sat ≤ Hamilton-Ut minden v´altoz´ohoz l´etrehozunk egy ´ert´ekv´alaszt´o gadgetet, az xi -hez tartoz´o k´et p´arhuzamos ´elt xi -vel ill. ¬xi -vel c´ımk´ezz¨ uk; minden kl´ozhoz l´etrehozunk egy h´aromsz¨ oget, az `1 ∨ `2 ∨ `3 kl´ozhoz l´etrehozott h´aromsz¨ og ´eleit rendre `1 -gyel, `2 -vel ´es `3 -mal c´ımk´ezz¨ uk; felvesz¨ unk m´eg k´et tov´abbi cs´ ucsot; az ellent´etes liter´alokkal c´ımk´ezett ´elek k¨ oz¨ ott XOR gadgetet hozunk l´etre; az ´ert´ekv´alaszt´o gadgeteket l´ancba k¨ otj¨ uk; a h´aromsz¨ogek cs´ ucsaib´ ol, az utols´ o ´ert´ekv´alaszt´o cs´ ucsb´ol ´es m´eg egy plusz cs´ ucsb´ ol pedig egyetlen nagy klikket k´esz´ıt¨ unk; v´eg¨ ul az el˝oz˝o pontbeli plusz cs´ ucsb´ ol m´eg egy u ´j cs´ ucsba Bonyolults´ agelm´ elet l´ep¨ unk.
´ P´elda 3Sat ≤ Hamilton-Ut Legyen ϕ = (x1 ∨ ¬x2 ∨ ¬x3 ) ∧ (¬x1 ∨ x2 ∨ ¬x3 ) ∧ (x1 ∨ x2 ∨ x3 ). Akkor a kapott gr´af: ¬x3
x1 ¬x2
x3
¬x3
x2
¬x2
x1
¬x1
¬x3
¬x1 x2
x3
x1 x2
Tov´abb´a, a k´ek cs´ ucsokat p´aronk´ent ¨ osszek¨ otj¨ uk, a h´aromsz¨ogek ´elei ´es az azonos c´ımk´ej˝ u ´ert´ekv´alaszt´ o ´elek k¨ oz´e a ⊕ gadgetet illesztj¨ uk. Bonyolults´ agelm´ elet
´ ≤P Tsp(E), ´ıgy a Tsp(E) probl´ema ´Igy, mivel Hamilton-Ut NP-teljes. T´etel ´s probl´ema NP-teljes. A 3-Sz´ıneze
Bonyolults´ agelm´ elet
´ ≤P Tsp(E), ´ıgy a Tsp(E) probl´ema ´Igy, mivel Hamilton-Ut NP-teljes. T´etel ´s probl´ema NP-teljes. A 3-Sz´ıneze Megjegyz´es
Bonyolults´ agelm´ elet
´ ≤P Tsp(E), ´ıgy a Tsp(E) probl´ema ´Igy, mivel Hamilton-Ut NP-teljes. T´etel ´s probl´ema NP-teljes. A 3-Sz´ıneze Megjegyz´es ´s probl´ema P-ben van. A 2-Sz´ıneze
Bonyolults´ agelm´ elet
´ ≤P Tsp(E), ´ıgy a Tsp(E) probl´ema ´Igy, mivel Hamilton-Ut NP-teljes. T´etel ´s probl´ema NP-teljes. A 3-Sz´ıneze Megjegyz´es ´s probl´ema P-ben van. A 2-Sz´ıneze ´s probl´ema trivi´alis s´ıkbarajzolhat´ A 4-Sz´ıneze o gr´afokra.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´s: ¨ 3Sat ≤ 3-Sz´ıneze otlet G
R B
x1
x2
x3
xn ...
¬x1
¬x2
¬x3
¬xn
´ıgy minden liter´al sz´ıne R (=,,hamis”) vagy G (=,,igaz”) sz´ın´evel kell megegyezzen, komplementere pedig egy m´asikkal ⇒ ki´ert´ekel´es `1
`2
`3
G
R
Ellen˝orizhet˝o: ha mindh´arom liter´al R sz´ın´et kapja, a plusz hat cs´ ucsot nem lehet helyesen 3-sz´ınezni, ha viszont van k¨ozt¨ uk G sz´ın˝ u, akkor igen Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ rmas´ıta ´s Ha Adott: H´arom azonos m´eret˝ u halmaz, F (fi´ uk), L (l´anyok), H (h´azak), ´es egy R ⊆ F × L × H rel´aci´ o. K´erd´es: Megadhat´ o-e az R-beli h´armasok egy olyan r´eszhalmaza, melyben minden fi´ u, l´any ´es h´az pontosan egyszer szerepel?
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ rmas´ıta ´s Ha Adott: H´arom azonos m´eret˝ u halmaz, F (fi´ uk), L (l´anyok), H (h´azak), ´es egy R ⊆ F × L × H rel´aci´ o. K´erd´es: Megadhat´ o-e az R-beli h´armasok egy olyan r´eszhalmaza, melyben minden fi´ u, l´any ´es h´az pontosan egyszer szerepel? ´ rmas´ıta ´ s ∈ NP. Vil´agos, hogy Ha
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ rmas´ıta ´s Ha Adott: H´arom azonos m´eret˝ u halmaz, F (fi´ uk), L (l´anyok), H (h´azak), ´es egy R ⊆ F × L × H rel´aci´ o. K´erd´es: Megadhat´ o-e az R-beli h´armasok egy olyan r´eszhalmaza, melyben minden fi´ u, l´any ´es h´az pontosan egyszer szerepel? ´ rmas´ıta ´ s ∈ NP. Vil´agos, hogy Ha T´etel ´ rmas´ıta ´ s probl´ema NP-teljes. A Ha
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ rmas´ıta ´s Ha Adott: H´arom azonos m´eret˝ u halmaz, F (fi´ uk), L (l´anyok), H (h´azak), ´es egy R ⊆ F × L × H rel´aci´ o. K´erd´es: Megadhat´ o-e az R-beli h´armasok egy olyan r´eszhalmaza, melyben minden fi´ u, l´any ´es h´az pontosan egyszer szerepel? ´ rmas´ıta ´ s ∈ NP. Vil´agos, hogy Ha T´etel ´ rmas´ıta ´ s probl´ema NP-teljes. A Ha Megjegyz´es ´ ros´ıta ´ s ∈ P. Pa Bonyolults´ agelm´ elet
´s Halmazlefede Adott: Egy U halmaz r´eszhalmazainak C = (S1 , . . . , Sn ) rendszere ´es egy K sz´am. K´erd´es: Kiv´alaszthat´ o-e K darab az Si -k k¨ oz¨ ul u ´gy, hogy ezek egyes´ıt´ese U ?
Bonyolults´ agelm´ elet
´s Halmazlefede Adott: Egy U halmaz r´eszhalmazainak C = (S1 , . . . , Sn ) rendszere ´es egy K sz´am. K´erd´es: Kiv´alaszthat´ o-e K darab az Si -k k¨ oz¨ ul u ´gy, hogy ezek egyes´ıt´ese U ? ´s Halmazpakola Adott: Egy U halmaz r´eszhalmazainak C = (S1 , . . . , Sn ) rendszere ´es egy K sz´am. K´erd´es: Kiv´alaszthat´ o-e az Si -k k¨ oz¨ ul K darab, p´aronk´ent diszjunkt halmaz?
Bonyolults´ agelm´ elet
´s Halmazlefede Adott: Egy U halmaz r´eszhalmazainak C = (S1 , . . . , Sn ) rendszere ´es egy K sz´am. K´erd´es: Kiv´alaszthat´ o-e K darab az Si -k k¨ oz¨ ul u ´gy, hogy ezek egyes´ıt´ese U ? ´s Halmazpakola Adott: Egy U halmaz r´eszhalmazainak C = (S1 , . . . , Sn ) rendszere ´es egy K sz´am. K´erd´es: Kiv´alaszthat´ o-e az Si -k k¨ oz¨ ul K darab, p´aronk´ent diszjunkt halmaz? ´s Ha ´ rmasokkal Pontos Lefede Adott: Egy 3m elem˝ u U halmaz ´es 3-elem˝ u r´eszhalmazainak (S1 , . . . , Sn ) rendszere. K´erd´es: Kiv´alaszthat´ o-e m darab Si u ´gy, hogy ezek egyes´ıt´ese U ? (A kiv´alasztott Si -k nyilv´an diszjunktak.) Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra
T´etel ´s, Halmazpakola ´ s, Pontos Lefede ´s A Halmazlefede ´ rmasokkal probl´em´ak NP-teljesek. Ha
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra
T´etel ´s, Halmazpakola ´ s, Pontos Lefede ´s A Halmazlefede ´ rmasokkal probl´em´ak NP-teljesek. Ha Bizony´ıt´as ´ rmas´ıta ´ s a Pontos Lefede ´ s Ha ´ rmasokkal speci´alis A Ha esete.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra
T´etel ´s, Halmazpakola ´ s, Pontos Lefede ´s A Halmazlefede ´ rmasokkal probl´em´ak NP-teljesek. Ha Bizony´ıt´as ´ rmas´ıta ´ s a Pontos Lefede ´ s Ha ´ rmasokkal speci´alis A Ha esete. ´ s Ha ´ rmasokkal a Halmazlefede ´s, A Pontos Lefede ´ s speci´alis esete is. valamint a Halmazpakola
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer.
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer. K´erd´es: L´etezik-e eg´esz ´ert´ek˝ u megold´as?
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer. K´erd´es: L´etezik-e eg´esz ´ert´ek˝ u megold´as? ´s felfoghat´ A Halmazlefede o az ´ ´ ´ ˝ ´ s speci´alis esetek´ent: Egesz Erteku Programoza
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer. K´erd´es: L´etezik-e eg´esz ´ert´ek˝ u megold´as? ´s felfoghat´ A Halmazlefede o az ´ ´ ´ ˝ ´ s speci´alis esetek´ent: Egesz Erteku Programoza n X Ax ≥ 1, xi ≤ B, 0 ≤ xi ≤ 1, i=1
ahol A oszlopai a halmazrendszer elemeinek felelnek meg.
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer. K´erd´es: L´etezik-e eg´esz ´ert´ek˝ u megold´as? ´s felfoghat´ A Halmazlefede o az ´ ´ ´ ˝ ´ s speci´alis esetek´ent: Egesz Erteku Programoza n X Ax ≥ 1, xi ≤ B, 0 ≤ xi ≤ 1, i=1
ahol A oszlopai a halmazrendszer elemeinek felelnek meg. Azt is meg lehet mutatni, hogy az ´ e ´sz Ert ´ku ˝ Programoza ´ s NP-ben van. Ege
Bonyolults´ agelm´ elet
´ e ´sz Ert ´ ku ˝ Programoza ´s Ege Adott: Egy n-v´altoz´os, eg´esz egy¨ utthat´ os line´aris egyenl˝otlens´eg-rendszer. K´erd´es: L´etezik-e eg´esz ´ert´ek˝ u megold´as? ´s felfoghat´ A Halmazlefede o az ´ ´ ´ ˝ ´ s speci´alis esetek´ent: Egesz Erteku Programoza n X Ax ≥ 1, xi ≤ B, 0 ≤ xi ≤ 1, i=1
ahol A oszlopai a halmazrendszer elemeinek felelnek meg. Azt is meg lehet mutatni, hogy az ´ e ´sz Ert ´ku ˝ Programoza ´ s NP-ben van. Ege T´etel ´ e ´sz Ert ´ku ˝ Programoza ´ s probl´ema NP-teljes. Az Ege Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra
´szleto ¨ sszeg probl´ema A Re
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra
´szleto ¨ sszeg probl´ema A Re Adott: a1 , . . . , an pozit´ıv eg´eszek ´es egy K > 0 c´elsz´am.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra
´szleto ¨ sszeg probl´ema A Re Adott: a1 , . . . , an pozit´ıv eg´eszek ´es egy K > 0 c´elsz´am. K´erd´es: Kiv´alaszthat´o-e az ai -k k¨ oz¨ ul n´eh´any elem u ´gy, hogy o¨sszeg¨ uk K legyen?
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra
´szleto ¨ sszeg probl´ema A Re Adott: a1 , . . . , an pozit´ıv eg´eszek ´es egy K > 0 c´elsz´am. K´erd´es: Kiv´alaszthat´o-e az ai -k k¨ oz¨ ul n´eh´any elem u ´gy, hogy o¨sszeg¨ uk K legyen? T´etel ´szleto ¨ sszeg probl´ema NP-teljes. A Re Az NP-belis´eg vil´agos, az NP-neh´ezs´eget a 3Satr´ol val´o visszavezet´essel igazoljuk.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 .
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm .
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek:
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek: ti ´es fi els˝ o m jegye csupa 0, kiv´eve az i. jegyet, ami 1-es;
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek: ti ´es fi els˝ o m jegye csupa 0, kiv´eve az i. jegyet, ami 1-es; ti utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel xi , egy´ebk´ent 0;
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek: ti ´es fi els˝ o m jegye csupa 0, kiv´eve az i. jegyet, ami 1-es; ti utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel xi , egy´ebk´ent 0; fi utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel ¬xi , egy´ebk´ent 0.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek: ti ´es fi els˝ o m jegye csupa 0, kiv´eve az i. jegyet, ami 1-es; ti utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel xi , egy´ebk´ent 0; fi utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel ¬xi , egy´ebk´ent 0.
Tov´abb´a, ai = bi = 10i minden i = 1, . . . , n eset´en.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´szleto ¨ sszeg 3Sat ≤ Re Legyen ϕ = c1 ∧ . . . ∧ cn egy 3CNF, ci = `i,1 ∨ `i,2 ∨ `i,3 . A ϕ-beli v´altoz´ok legyenek x1 , . . . , xm . ´szleto ¨ sszeg probl´ema egy p´eld´any´at, Ebb˝ol elk´esz´ıtj¨ uk a Re melyben n + m-jegy˝ u (!) sz´amok szerepelnek. xi -b˝ol a ti ´es fi sz´amok k´esz¨ ulnek: ti ´es fi els˝ o m jegye csupa 0, kiv´eve az i. jegyet, ami 1-es; ti utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel xi , egy´ebk´ent 0; fi utols´ o n jegye k¨ oz¨ ul az m + k. akkor 1-es, ha ck -ban szerepel ¬xi , egy´ebk´ent 0.
Tov´abb´a, ai = bi = 10i minden i = 1, . . . , n eset´en. Az eredm´eny: a {fi , ti : 1 ≤ i ≤ m} ∪ {ai , bi : 1 ≤ i ≤ n} halmaz ´es a K = 11 . . . 133 . . . 3 c´elsz´am (m darab 1-es, majd n darab 3-as). Bonyolults´ agelm´ elet
P´elda Ha ϕ = (x1 ∨ ¬x2 ∨ x3 ) ∨ (x1 ∨ ¬x2 ∨ x4 ) ∨ (¬x1 ∨ x2 ∨ ¬x4 ): t1 = 1000110 f1 = 1000001 t2 = 0100001 f2 = 0100110 t3 = 0010100 f3 = 0010000 t4 = 0001010 f4 = 0001001 a1 = b1 = 0000100 a2 = b2 = 0000010 a3 = b3 = 0000001 K = 1111333 Bonyolults´ agelm´ elet
P´elda Ha ϕ = (x1 ∨ ¬x2 ∨ x3 ) ∨ (x1 ∨ ¬x2 ∨ x4 ) ∨ (¬x1 ∨ x2 ∨ ¬x4 ): t1 = 1000110 f1 = 1000001
t1 ´es f1 k¨ oz¨ ul pontosan az egyiket kell v´alasszuk (K els˝ o jegye miatt);
t2 = 0100001 f2 = 0100110 t3 = 0010100 f3 = 0010000 t4 = 0001010 f4 = 0001001 a1 = b1 = 0000100 a2 = b2 = 0000010 a3 = b3 = 0000001 K = 1111333 Bonyolults´ agelm´ elet
P´elda Ha ϕ = (x1 ∨ ¬x2 ∨ x3 ) ∨ (x1 ∨ ¬x2 ∨ x4 ) ∨ (¬x1 ∨ x2 ∨ ¬x4 ): t1 = 1000110 f1 = 1000001 t2 = 0100001 f2 = 0100110 t3 = 0010100
t1 ´es f1 k¨ oz¨ ul pontosan az egyiket kell v´alasszuk (K els˝ o jegye miatt); ´altal´aban ti ´es fi k¨ oz¨ ul is pontosan az egyiket – ti v´alaszt´asa feleljen meg az xi = 1, fi v´alaszt´asa az xi = 0 ´ert´ekad´asnak;
f3 = 0010000 t4 = 0001010 f4 = 0001001 a1 = b1 = 0000100 a2 = b2 = 0000010 a3 = b3 = 0000001 K = 1111333 Bonyolults´ agelm´ elet
P´elda Ha ϕ = (x1 ∨ ¬x2 ∨ x3 ) ∨ (x1 ∨ ¬x2 ∨ x4 ) ∨ (¬x1 ∨ x2 ∨ ¬x4 ): t1 = 1000110 f1 = 1000001 t2 = 0100001 f2 = 0100110 t3 = 0010100 f3 = 0010000 t4 = 0001010 f4 = 0001001
t1 ´es f1 k¨ oz¨ ul pontosan az egyiket kell v´alasszuk (K els˝ o jegye miatt); ´altal´aban ti ´es fi k¨ oz¨ ul is pontosan az egyiket – ti v´alaszt´asa feleljen meg az xi = 1, fi v´alaszt´asa az xi = 0 ´ert´ekad´asnak; ezzel az m + j. jegyek mindegyike 0, 1, 2 vagy 3 lesz j = 1, . . . , n-re, annak f¨ uggv´eny´eben, hogy cj -ben 0, 1, 2 vagy 3 liter´al v´alt igazz´a;
a1 = b1 = 0000100 a2 = b2 = 0000010 a3 = b3 = 0000001 K = 1111333 Bonyolults´ agelm´ elet
P´elda Ha ϕ = (x1 ∨ ¬x2 ∨ x3 ) ∨ (x1 ∨ ¬x2 ∨ x4 ) ∨ (¬x1 ∨ x2 ∨ ¬x4 ): t1 = 1000110 f1 = 1000001 t2 = 0100001 f2 = 0100110 t3 = 0010100 f3 = 0010000 t4 = 0001010 f4 = 0001001 a1 = b1 = 0000100 a2 = b2 = 0000010 a3 = b3 = 0000001 K = 1111333
t1 ´es f1 k¨ oz¨ ul pontosan az egyiket kell v´alasszuk (K els˝ o jegye miatt); ´altal´aban ti ´es fi k¨ oz¨ ul is pontosan az egyiket – ti v´alaszt´asa feleljen meg az xi = 1, fi v´alaszt´asa az xi = 0 ´ert´ekad´asnak; ezzel az m + j. jegyek mindegyike 0, 1, 2 vagy 3 lesz j = 1, . . . , n-re, annak f¨ uggv´eny´eben, hogy cj -ben 0, 1, 2 vagy 3 liter´al v´alt igazz´a; ha az m + j. jegy 3, akkor j´o, ha 2, akkor v´alasszuk ki m´eg mondjuk aj -t, ha 1, akkor aj -t ´es bj -t is, ha 0, akkor nem tudjuk ezen a jegyen el´erni a c´elsz´amot Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ e ´sz Ert ´ku ˝ Programoza ´ s egy m´asik speci´alis esete: Az Ege
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ e ´sz Ert ´ku ˝ Programoza ´ s egy m´asik speci´alis esete: Az Ege ´ tizsa ´k Ha
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ e ´sz Ert ´ku ˝ Programoza ´ s egy m´asik speci´alis esete: Az Ege ´ tizsa ´k Ha Adott: n elem mindegyik´enek wi s´ ulya ´es ci ´ert´eke, valamint W ´es C.
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ e ´sz Ert ´ku ˝ Programoza ´ s egy m´asik speci´alis esete: Az Ege ´ tizsa ´k Ha Adott: n elem mindegyik´enek wi s´ ulya ´es ci ´ert´eke, valamint W ´es C. K´erd´es: Kiv´alaszthat´o-e ism´etl´es n´elk¨ ul n´eh´any elem u ´gy, hogy ¨ossz´ert´ek¨ uk ≥ C ´es ¨osszs´ ulyuk ≤ W ?
Bonyolults´ agelm´ elet
NP-teljes probl´em´ak halmazokra ´es sz´amokra ´ e ´sz Ert ´ku ˝ Programoza ´ s egy m´asik speci´alis esete: Az Ege ´ tizsa ´k Ha Adott: n elem mindegyik´enek wi s´ ulya ´es ci ´ert´eke, valamint W ´es C. K´erd´es: Kiv´alaszthat´o-e ism´etl´es n´elk¨ ul n´eh´any elem u ´gy, hogy ¨ossz´ert´ek¨ uk ≥ C ´es ¨osszs´ ulyuk ≤ W ? T´etel ´ tizsa ´ k probl´ema NP-teljes. A Ha ¨ Otlet ´szleto ¨ sszeg probl´em´aban az ai ´ert´ekekb˝ A Re ol rendre k´esz´ıts¨ unk egy t´argyat wi = ci = ai s´ ullyal ´es ´ert´ekkel, tov´abb´a legyen C = W = K, a c´elsz´am. Bonyolults´ agelm´ elet
¨ Osszefoglal´ as ´ NP-teljes. ´Igy a Megmutattuk, hogy a Hamilton-Ut TSP(E) is az. ´s NP-teljes. Megmutattuk, hogy a 3 − Sz´ıneze Defini´altuk a k¨ovetkez˝ o probl´em´akat ´es bel´attuk NP-teljess´eg¨ uket: ´ rmas´ıta ´s Ha ´s Ha ´ rmasokkal Pontos Lefede ´s Halmazlefede ´s Halmazpakola ´szleto ¨ sszeg Re ´ tizsa ´k Ha
´ e ´sz Ert ´ku ˝ Programoza ´ s probl´em´at ´es Defini´altuk az Ege bel´attuk, hogy NP-neh´ez.
Bonyolults´ agelm´ elet
