A számítástudomány alapjai - Ismert NP teljes problémák

Ez az oldal a korábbi SCH wikiről lett áthozva.

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"}%

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 $\exists$ k db ftlen pont}

3-SZÍN $\prec$ MAXFTLEN

Maxklikk

MAXKLIKK = {(G, k): G-ben $\exists$ k méretű klikk}

MAXFTLEN $\prec$ MAXKLIKK $f:(G,k)\rightarrow ({\overline {G}},k)$

Éllefogás

Éllefogás = {(G, k): G-ben $\exists$ k méretű éllefogó halmaz}

MAXFTLEN $\prec$ Éllefogás $f:(G,k)\rightarrow (G,|V(G)|-k)$

Irányított Hamilton-kör

Olyan gráfok, amikben van ir. H-kör

Éllefogás $\prec$ IH

Hamilton-kör

Olyan gráfok, amikben van H-kör

IH $\prec$ 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 $\exists \leq$ k súlyú H-kör

H $\prec$ 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 = $\{(s_{1}..s_{m},k):\exists I\subseteq \{1..m\}:\sum \limits _{i\in I}s_{i}=k\}$

X3C $\prec$ RH

Partíció

Adott számok egy halmaza. Felbontható-e két egyforma összegű részhalmazra?

RH $\prec$ 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ó $\prec$ Láda

-- SzaMa - 2005.05.23.
-- D-nee - 2006.06.11.