nondeterministic polynomial time

nondeterministic polynomial time (tsz. nondeterministic polynomial times)

1. (informatika) nemdeterminisztikus polinomiális idő

A számításelmélet egyik legfontosabb komplexitás‐osztálya az NP, azaz a „nemdeterminisztikus polinom‐idő” problémák gyűjteménye. Az NP‐beli problémák olyan döntési feladatok, amelyekre — ha valaki egy „bizonyítékot” (certificate) ad — polinomiális idő alatt ellenőrizhető, hogy a válasz helyes‐e.

A NP elnevezés a nondeterministic polynomial time kifejezésből ered. Bár a való világban a nem‐determinista számítógép (amely egyszerre „megpróbál” minden lehetőséget) nem létezik, az elméleti modell igen hatékonyan ragadja meg azokat a feladatokat, amelyek meghívásra „szerencsére” gyorsan ellenőrizhetők, de megoldásuk látszólag nehéz.

Egy döntési probléma (igen/nem kérdés) ${\textstyle L}$ akkor tartozik az NP‐be, ha létezik egy polinomiális időben futó determinisztikus Turing‐gép (ellenőrző gép) ${\textstyle V}$ és egy polinom ${\textstyle p(n)}$, hogy minden bemenetre ${\textstyle x}$ pontosan az alábbi feltételek igazak:

1. „Igen” eset (${\textstyle x\in L}$): létezik egy bizonyíték ${\textstyle w\in \{0,1\}^{p(|x|)}}$ (certificate), amire

   $${\displaystyle V(x,w)=igen}$$

   futási ideje legfeljebb ${\textstyle O{\bigl (}|x|^{k}{\bigr )}}$ egy rögzített ${\textstyle k}$-ra.

2. „Nem” eset (${\textstyle x\notin L}$): minden ${\textstyle w}$ esetén

   $${\displaystyle V(x,w)=nem}$$

Itt ${\textstyle |x|}$ a bemenet hosszát (bit‐sorrendben), ${\textstyle w}$ hossza pedig legfeljebb polinom ${\textstyle p(|x|)}$. Az ellenőrzési folyamat tehát determinisztikus és polinom időben zajlik.

NP‐t alternatív módon úgy is definiálhatjuk, hogy NP‐ben vannak azok a problémák, amelyeket egy nem‐determinista Turing‐gép (NTM) polinomiális lépés alatt meg tud oldani:

• A nem‐determinista gép egy adott állapotból egyszerre, „párhuzamosan” több ágra (lehetséges folytatásokra) léphet.
• Ha legalább egy „ágon” sikeresen elfogadja a bemenetet (állapotaiban elér egy elfogadó állapotot) legfeljebb ${\textstyle O(|x|^{k})}$ lépés alatt, a gép „igen” döntést ad.
• Ha semelyik ág nem fogadja el, akkor „nem” a válasz.

Habár ez a modell elméleti, jól megragadja azt a tulajdonságot, hogy „valami” szerencsésen gyorsan megtalálhatja a jó megoldást, míg determinisztikus gépen hasonló feltételekkel nem biztos, hogy polinom idő alatt megoldjuk.

• A P osztály azokat a döntési feladatokat tartalmazza, amelyeket determinisztikus Turing‐géppel polinomiális idő alatt meg tudunk oldani.
• Nyilvánvalóan ${\textstyle \mathrm {P} \subseteq \mathrm {NP} }$, hiszen ha megoldjuk „magától” polinom idő alatt, akkor a megoldást mint bizonyítékot ellenőrzéskor is felhasználhatjuk.
• A híres P vs. NP kérdés arra vonatkozik, hogy vajon van‐e olyan determinisztikus polinom‐idő algoritmus azokhoz a feladatokhoz, amelyeket ma csak nem‐determinista modellben tartunk polinom idejűnek. A legtöbb szakértő szerint ${\textstyle P\neq NP}$, de ez ma is nyitott probléma.

1. SAT (boole‐kielégíthetőség)
   • Bemenet: egy Boole‐kifejezés CNF formában.
   • Kérdés: van‐e változó‐értékadás, ami a kifejezést igazra értékeli?
   • Bizonyíték: egy változó‐értékadás; ellenőrzés polinom időben.
2. Hamilton‐út döntés
   • Bemenet: egyszerű gráf ${\textstyle G}$, csúcs‐szám ${\textstyle n}$.
   • Kérdés: van‐e olyan egyszer végigjáró út, ami minden csúcsot pontosan egyszer érint (Hamilton‐út)?
   • Bizonyíték: a csúcslánc felsorolása ${\textstyle (v_{1},v_{2},\dots ,v_{n})}$; ellenőrzés ${\textstyle O(n^{2})}$-ben.
3. Subset Sum
   • Bemenet: egész számok halmaza és célösszeg ${\textstyle T}$.
   • Kérdés: létezik‐e részhalmaz, amelynek összege ${\textstyle T}$?
   • Bizonyíték: a megfelelő részhalmaz indexei; összeadás polinom időben.
4. Vertex Cover döntés
   • Bemenet: gráf és egész ${\textstyle k}$.
   • Kérdés: van‐e ${\textstyle k}$ csúcs, amelyek érintenek minden élt?
   • Bizonyíték: a csúcshalmaz; él‐ellenőrzés polinom időben.

• NP‐teljes: NP‐ben vannak és NP‐nehézek (minden NP‐feladat polinom időben visszavezethető rájuk).
• Ezek a „legtöbb NP‐feladat nehézségi csúcsai”: például 3‐SAT, Hamilton‐út, Vertex Cover.
• Ha egy NP‐teljes feladatot determinisztikusan polinom időben megoldanánk, akkor ${\textstyle P=NP}$ teljesen.

A NP‐teljesség bizonyítása rendszerint két lépésben történik:

1. Mutassuk meg, hogy a probléma NP‐ben van (ellenőrizhetőség).
2. Vegyük egy már ismert NP‐teljes feladatot, és konstruáljunk polinomiális redukciót rá.

Mivel a NP‐teljes feladatok várhatóan nem oldhatók meg polinom időben, három fő stratégiát alkalmazunk:

1. Pseudopolinomiális algoritmusok – A futásidő a bemeneti numerikus értékek (pl. célösszeg) függvénye, nem „kvázi‐polinom”, de gyakorlati paraméterekkel működik (Subset Sum, Knapsack).
2. Approximation (közelítő) algoritmusok – PTAS, FPTAS: ${\textstyle \varepsilon }$-pontosság garanciával, futásidő polinomális a bemeneti méretben és ${\textstyle 1/\varepsilon }$-ben.
3. Heurisztikák és metaheurisztikák – Greedy, lokális keresés, szimulált hőkezelés, genetikus algoritmusok — hatékonyak nagy inputokra, de nincs optimális garancia.

• A kriptográfia: az RSA, DSA és hasonló rendszerek biztonsága a diszkrét logaritmus és faktorizáció NP‐nehézségén alapszik (bár nem tudjuk, hogy NP‐ben vannak‐e).
• A tudományos kutatás: a P vs. NP kérdés Az Egyik legnagyobb nyitott probléma, amely a számítástudomány alapjait érinti.
• Az ipari alkalmazások: ütemezés, hálózat‐tervezés, portfólió‐optimalizálás, genetikai algoritmusok, adatbányászat — ezekben gyakran NP‐beli alfeladatok bukkannak fel.

• Az NP azokat a döntési feladatokat foglalja magába, melyekre polinomiális időben ellenőrizhető egy „bizonyíték”.
• Formálisan nem‐determinista Turing‐gép polinomiális futási idejét modellezi.
• NP‐teljes problémák a legnehezebbek NP‐ben; megoldásuk ${\textstyle P=NP}$-t implikálna.
• Gyakorlatban közelítő, pseu­do­polinomiális és heurisztikus módszerekkel közelítjük őket.

Az NP osztály és a nem‐determinista polinom‐idő modell alapozza meg a számítástudomány elméleti és gyakorlati kutatásának egyik legerőteljesebb keretrendszerét.

• nondeterministic polynomial time - Szótár.net (en-hu)
• nondeterministic polynomial time - Sztaki (en-hu)
• nondeterministic polynomial time - Merriam–Webster
• nondeterministic polynomial time - Cambridge
• nondeterministic polynomial time - WordNet
• nondeterministic polynomial time - Яндекс (en-ru)
• nondeterministic polynomial time - Google (en-hu)
• nondeterministic polynomial time - Wikidata
• nondeterministic polynomial time - Wikipédia (angol)