A számítástudomány alapjai - Ismert NP teljes problémák
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.
Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót
%TOC{depth="2"}%
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 pontosan 3 változót tartalmaznak. Pl (x V -x V y) ^ (z V -y V x)
Szerintem pontosan helyett legfeljebb. -- kronik - 2005.06.09.
Szerintem viszont a pontosan a helyes meghatározás, hiszen ha megengedett 3-nál kevesebb tagból álló VAGY kapcsolat (vagyis akár az is, hogy mindegyik csak 2 tagból áll), akkor az már polinom időben is számolható lenne (lásd 2-SAT nyelv TK 277. o.) -- NeoXon - 2005.06.16.
Szerintem viszont legfeljebb: Ugyanis: vagyél egy olyat amiben az összes csupa 3 tagú. vagyolj hozzá egy olyat, hogy X meg egy olyat, hogy X negált. ettől azt hiszem nem fogod tudni megmondani, hogy kielégíthető-e. --> NP teljes maradt --> ez bizony 3-Sat. (De egyébként a könyvben is legfeljebb 3-ként van definiálva.) -- TitCar - 2006.06.18.
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
