A számítástudomány alapjai - Ismert NP teljes problémák
Tartalomjegyzék
SAT nyelv
Olyan Boole formulák (konjunktív normál formában felírva), amelyek kielégíthetőek. (satisfyable - van 1 az igazságtáblában).
Erről bizonyítottuk, hogy NP teljes
3-SAT
Olyan Boole formulák (konjunktív normál formában felírva), amelyek kielégíthetőek, és a VAGY tömbök legfeljebb 3 változót tartalmaznak. Például: (x V -x V y) ^ (z V -y V x)
A SAT-ot vezettük vissza rá, ezért NP teljes
3 színnel színezhető gráfok
Olyan gráfok, melyek 3 színnel kiszínezhetőek.
A 3-SAT-ot vezettük vissza rá, ezért NP teljes
Maxfüggetlen
MAXFTLEN = {(G, k): G-ben [math]\exists[/math] k db ftlen pont}
3-SZÍN [math]\prec[/math] MAXFTLEN
Maxklikk
MAXKLIKK = {(G, k): G-ben [math]\exists[/math] k méretű klikk}
MAXFTLEN [math]\prec[/math] MAXKLIKK [math]f: (G, k) \rightarrow (\overline{G}, k)[/math]
Éllefogás
Éllefogás = {(G, k): G-ben [math]\exists[/math] k méretű éllefogó halmaz}
MAXFTLEN [math]\prec[/math] Éllefogás [math]f: (G, k) \rightarrow (G, |V(G)|-k)[/math]
Irányított Hamilton-kör
Olyan gráfok, amikben van ir. H-kör
Éllefogás [math]\prec[/math] IH
Hamilton-kör
Olyan gráfok, amikben van H-kör
IH [math]\prec[/math] H
Hamilton-út
Olyan gráfok, amikben van H-út
Gyakon a H-kört vezettük vissza rá, ezért NP teljes
A visszavezetés: gráfba vegyünk fel még A B C pontokat, legyen V egy eredeti pont. Kössük öszze A-V-t, B-C-t, és V minden szomszédját kössük össze B-vel. Ha ebben az új gráfban van H út, akkor az eredetiben van H kör. (Az út A-V-...-X-B-C, lesz, és V és X között megy él, tehát bezárható a H-kör)
Utazó ügynök
Utazóügynök = {(G, k): G irányítatlan, élsúlyozott, teljes gráf, melyben [math]\exists \leq[/math] k súlyú H-kör
H [math]\prec[/math] Utazóügynök
Hátizsák
Adott egy hátizsák mérete, és tárgyak értéke és mérete, és egy értékkorlát. Bele lehet-e pakolni legalább az értékkolrátnyi értéket? (Először a Horadric Cube-ot kell felvenni... :) )
(A probléma azért NP teljes, mert a hátizsák mérete is az input része. A számításigény a mérettel egyenesen arányos, az input hossza viszont csak a logaritmusával.)
Részhalmazösszeg
Hátizsák speciális esete, ahol a tárgyak mérete és értéke megegyezik: RH = [math]\{(s_{1}..s_{m}, k): \exists I \subseteq \{1..m\}: \sum\limits_{i \in I}s_{i} = k\}[/math]
X3C [math]\prec[/math] RH
Partíció
Adott számok egy halmaza. Felbontható-e két egyforma összegű részhalmazra?
RH [math]\prec[/math] Partíció
Ládapakolás
Adottak tárgyak méretei (racionális számok), és k. A tárgyak beleférnek-e k db egységnyi méretű dobozba?
Partíció [math]\prec[/math] Láda
