A számítástudomány alapjai - Ismert NP teljes problémák
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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \exists} k db ftlen pont}
3-SZÍN Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} MAXFTLEN
Maxklikk
MAXKLIKK = {(G, k): G-ben Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \exists} k méretű klikk}
MAXFTLEN Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} MAXKLIKK Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle f: (G, k) \rightarrow (\overline{G}, k)}
Éllefogás
Éllefogás = {(G, k): G-ben Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \exists} k méretű éllefogó halmaz}
MAXFTLEN Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} Éllefogás Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} IH
Hamilton-kör
Olyan gráfok, amikben van H-kör
IH Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \exists \leq} k súlyú H-kör
H Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \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 = Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{(s_{1}..s_{m}, k): \exists I \subseteq \{1..m\}: \sum\limits_{i \in I}s_{i} = k\}}
X3C Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} RH
Partíció
Adott számok egy halmaza. Felbontható-e két egyforma összegű részhalmazra?
RH Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \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ó Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \prec} Láda
