NP-complete problem

Angol

Főnév

NP-complete problem (tsz. NP-complete problems)

1. (informatika)

NP‐teljes (NP‐complete) problémák azok a döntési feladatok, melyek egyszerre NP‐ben vannak (azaz egy adott megoldás – „igen”‐válasz – polinomiális idő alatt ellenőrizhető) és NP‐nehézek (NP‐hard), vagyis bármely más NP‐probléma polinomiális időben visszavezethető rá (reduktálható).

---

1. Formális definíció

Egy döntési probléma ${\textstyle L}$ NP‐teljes, ha

1. ${\textstyle L\in }$ NP: létezik polinomiális idő alatt futó Turing‐gép, amely igazolja, hogy egy „igen”‐példa valóban megoldható (például bemutat egy hitelesítő bizonyítékot, „certificate”-et).

2. NP‐nehéz: minden ${\textstyle L'\in }$ NP esetén van olyan polinomiális időben számítható függvény ${\textstyle f}$, hogy

   $$x\in L'\quad \Longleftrightarrow \quad f(x)\in L.$$

   Ez a Karp‐redukció, amely azt mondja, hogy ${\textstyle L}$ legalább olyan nehéz, mint bármely más NP‐probléma.

---

2. Miért fontosak az NP‐teljesek?

• „Príma” NP‐nehéz feladatok: Ha találunk polinomiális algoritmust egyetlen NP‐teljes problémára, akkor minden NP‐probléma polinomiálisan megoldhatóvá válik, azaz ${\textstyle P=NP}$.
• Hard-tartomány: az NP‐teljes problémák valóságos rendszerekben gyakran előfordulnak (ütemezés, hálózatok, optimalizálás), és általában csak közelítő vagy heurisztikus eljárásokkal kezelhetők nagy méretekben.

---

3. Klasszikus NP‐teljes példák

1. Satisfiability (SAT) – Van‐e igazságérték‐-beállítás, amelyre egy Boole‐kifejezés igaz?
2. 3‐SAT – A SAT speciális esete, ahol a kifejezés konjunktív normálalakú, és minden diszjunkción pontosan három literál szerepel.
3. Vertex Cover – Adott gráfban létezik‐e ${\textstyle k}$ csúcs, amelyek érintik az összes élt?
4. Clique – Létezik‐e ${\textstyle k}$ csúcs, amelyek mind páronként összekötöttek?
5. Hamilton‐kör döntés – Létezik‐e zárt út egy gráfban, amely minden csúcsot pontosan egyszer érint?
6. Subset Sum – Megvan‐e olyan részhalmaz, amely összege egy adott ${\textstyle T}$?
7. Partition – Feloszthatók‐e a számok két csoportba, hogy az összegek egyenlők legyenek?
8. Travelling Salesman Problem (TSP) döntés – Van‐e Hamilton‐kör összköltsége ≤${\textstyle K}$?

Ezek a problémák Karp (1972) által publikált 21 NP‐teljes feladat közül csak néhány.

---

4. Redukciók és bizonyítások

• Karp‐redukció: polinomiális időben számítható leképezés ${\textstyle f\colon L'\to L}$, ami „megőrzi” a döntést.
• A legtöbb NP‐teljes probléma bizonyítása úgy történik, hogy megmutatjuk, hogyan lehet egy már ismert NP‐teljest (például 3-SAT) redukálni rá.

---

5. Közelítő algoritmusok és heurisztikák

Mivel NP‐teljes problémák nagyméretű példányait valós időben nem oldjuk meg pontosan, gyakran alkalmazunk:

1. Greedy és lokális keresés
2. Metaheurisztikák: genetikus algoritmus, szimulált hőkezelés
3. Approximation schemes
   • PTAS (Polynomial‐Time Approximation Scheme): minden ${\textstyle \varepsilon >0}$ mellett $ (1+)$-közelítő polinomiális időben.
   • FPTAS (Fully PTAS): polinomiális mind a bemeneti méretben, mind ${\textstyle 1/\varepsilon }$ függvényében.
4. Paraméterezett algoritmusok – Hatékonyak, ha a probléma egy bizonyos paramétere (pl. ${\textstyle k}$ mérete) kicsi.

---

6. Összefoglalás

• NP‐teljes problémák: NP‐beli és NP‐nehéz feladatok, melyekről feltételezik, hogy nem oldhatók meg polinomiálisan.
• A P vs. NP kérdés központi: ha egy NP‐teljeset polinomiálisan megoldunk, akkor ${\textstyle P=NP}$.
• Számtalan gyakorlati alkalmazásnál bukkan fel: tervezés, ütemezés, optimalizálás, titkosítás, hálózatok.
• Megközelítések: heurisztikák, közelítő séma és paraméterezett módszerek nélkülözhetetlenek a nagy példányokhoz.

További információk

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