NP-complete

Angol

Főnév

NP-complete (tsz. NP-completes)

1. (informatika) NP-teljes

NP-complete (magyarul: NP-teljes) problémák azok a döntési problémák, amelyek:

1. Az NP osztályba tartoznak: azaz polinomiális időben ellenőrizhető a megoldásuk,
2. NP-nehézek: azaz minden más NP-probléma polinomiális időben visszavezethető rájuk.

👉 Ez az osztály a „leghardcore-abb” nehézségi szintje annak, amit ellenőrizni könnyű, de megoldani nehéz.

---

🧠 1. Mi az NP?

• Az NP (nondeterministic polynomial time) osztály azon problémák halmaza, amelyekre, ha valaki ad egy megoldást, azt gyorsan (polinomiális időben) ellenőrizni tudjuk.

---

📐 2. Definíció: NP-complete

Egy döntési probléma akkor NP-complete, ha:

1. ${\textstyle L\in {\text{NP}}}$
2. Minden ${\textstyle L'\in {\text{NP}}}$ esetén: ${\textstyle L'\leq _{p}L}$, azaz van polinomiális időbeli redukció ${\textstyle L'}$-ből ${\textstyle L}$-be

---

📦 3. Mit jelent ez gyakorlatban?

• Ha bármelyik NP-teljes problémára találunk gyors (polinomiális idejű) algoritmust, akkor:

  $${\text{P}}={\text{NP}}$$

• Ez minden NP-probléma megoldhatóságát jelentené gyorsan.

• Jelenleg nincs ismert algoritmus egyetlen NP-teljes probléma gyors megoldására, és nem bizonyított, hogy nincs.

---

🔁 4. Redukció – a kulcsművelet

Ha meg tudjuk mutatni, hogy:

• Egy ismert NP-complete probléma polinomiális időben redukálható egy új problémára,
• és az új probléma is az NP-ben van,

akkor az új probléma is NP-complete.

---

🔧 5. Első NP-teljes probléma: SAT

A Cook–Levin-tétel (1971) szerint:

A SAT (kielégíthetőségi probléma) NP-teljes.

Ez volt az első bizonyítottan NP-complete probléma, és az összes többi ehhez viszonyítva vált NP-teljessé.

---

🧮 6. Klasszikus NP-complete problémák

Probléma	Rövid leírás
3-SAT	Logikai formula 3 literálos klauzulákból
Clique	Van-e ${\textstyle k}$-méretű klikk egy gráfban?
Vertex Cover	Lefedhető-e a gráf élei ${\textstyle k}$ csúccsal?
Hamiltonian cycle	Van-e zárt körút, ami minden csúcsot érint?
Subset sum	Van-e részhalmaz, amely adott összeget ad?
Knapsack (döntési változat)	Van-e olyan kiválasztás, amely nem lépi túl a súlyt és eléri az értéket?
Graph coloring	${\textstyle k}$ színnel színezhető-e a gráf szomszédos csúcsok nélkül?
TSP (döntési)	Van-e olyan körút, ami nem hosszabb ${\textstyle k}$-nál?

---

📊 7. Vizualizáció – komplexitási hierarchia

          +-------------------+
          |   NP-complete     | ← nagyon nehéz
          +--------+----------+
                   |
                 ⬇ Redukció
+------------+    +-------------+    +----------+
|    P       | ⊆  |     NP      | ⊆ | PSPACE   |
+------------+    +-------------+    +----------+

---

🛠️ 8. Mi történne, ha P = NP?

• Minden NP-complete probléma gyorsan megoldható lenne.
• Titkosítás (pl. RSA, ECC) elvesztené biztonságát.
• Számítási kreativitás (bizonyítás, optimalizálás, keresés) automatizálhatóvá válna.

De:

• A legtöbb szakértő úgy véli, hogy P ≠ NP.

---

🧾 9. Összefoglalás

Fogalom	Leírás
NP-complete	Az NP osztály „legnehezebb” problémái
Tulajdonság	NP-ben vannak, és minden NP-probléma redukálható rájuk
Kulcstechnika	Polinomiális időbeli redukció
Fontos példák	SAT, Clique, TSP, Knapsack, Graph Coloring
Tét	Ha bármelyik megoldható gyorsan, akkor P = NP

További információk

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