A számítástudomány alapjai - Ismert NP teljes problémá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 $\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