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

← Vissza az előző oldalra – A számítástudomány alapjai

Ezen az oldalon van összegyűjtve jónéhány NP teljes probléma - NEM teljes lista! Érdemes ZH készülés közben végigbogarászni, hogy mégis mik azok a problémák amikre visszavezetve a feladatot, bizonyítható hogy az szintén NP teljes probléma.

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