P versus NP problem

Millennium Prize Problems
Birch and Swinnerton-Dyer conjecture Hodge conjecture Navier–Stokes existence and smoothness P versus NP problem Poincaré conjecture (solved) Riemann hypothesis Yang–Mills existence and mass gap

Angol

Főnév

P versus NP problem (tsz. P versus NP problems)

1. (informatika)

A P ≟ NP probléma a számítástudomány és matematika egyik legmélyebb és legjelentősebb megoldatlan kérdése. Ez az ún. millenniumi problémák egyike, és a megoldásáért 1 millió dolláros jutalom jár (Clay Mathematics Institute).

---

🧠 1. A probléma lényege

Vajon minden olyan probléma, amelynek megoldása gyorsan ellenőrizhető (NP), gyorsan meg is oldható (P)?

Formálisan:

P ≟ NP

---

📚 2. Mit jelent P és NP?

Osztály	Jelentés
P	Polinomiális időben megoldható problémák
NP	Polinomiális időben ellenőrizhető problémák

📌 Az NP nem azt jelenti, hogy lassú, hanem azt, hogy gyorsan ellenőrizhető, ha valaki ad egy megoldást.

---

🔍 3. Példák

Problémák P-ben:

• Két szám összeadása
• Lista rendezése
• Legkisebb közös osztó keresése

Problémák NP-ben, de nem ismert, hogy P-ben vannak-e:

• Sudoku megoldása
• 3-SAT (logikai formula kielégíthetősége)
• Travelling Salesman (döntési változat)
• Knapsack (döntési változat)

---

🧩 4. Ha P = NP…

• Minden NP-problémát gyorsan meg tudnánk oldani.
• Problémák, amelyekre ma csak heurisztikáink vannak, teljesen automatizálhatóvá válnának.
• Kriptográfia (RSA, ECC, hash-függvények) megdőlne.
• Automatikus bizonyítás, tervezés, mesterséges intelligencia hatalmasat ugrana.

---

🚫 5. Ha P ≠ NP…

• Megerősítené azt a tapasztalatot, hogy bizonyos problémák természetesen nehezek.
• A jelenlegi titkosítási módszerek továbbra is biztonságosak lennének.
• Sok alkalmazási területen továbbra is szükség van közelítő és heurisztikus megoldásokra.

---

🧮 6. Egy egyszerű példa: Sudoku

• Bemenet: egy részben kitöltött Sudoku tábla.
• Kérdés: van-e olyan kitöltés, ami szabályos?

Ez egy NP-probléma:

• Ha valaki megad egy megoldást, 0.01 másodperc alatt ellenőrizheted.
• A megoldás megtalálása viszont nehéz lehet – hacsak nem P = NP.

---

🧪 7. Mit tudunk jelenleg?

• Több ezer probléma ismert, amelyek:
  • NP-ben vannak
  • és NP-teljesek (pl. 3-SAT, Clique, TSP)
• Ha bármelyiket meg tudnánk oldani polinomiális időben, akkor P = NP lenne.
• De eddig senki sem bizonyította egyik irányt sem.

---

📜 8. Formális megfogalmazás

Keress bizonyítást arra, hogy:

• Létezik olyan ${\textstyle L\in {\text{NP}}}$, amely nincs ${\textstyle {\text{P}}}$-ben, vagy
• Minden ${\textstyle L\in {\text{NP}}}$ benne van ${\textstyle {\text{P}}}$-ben.

Ez a kérdés Turing-gépek, redukciók, és polinomiális idő fogalmával értelmezett.

---

🧾 9. Összefoglalás

Fogalom	Jelentés
P	Problémák, amelyekre van gyors (polinomiális idejű) megoldás
NP	Problémák, amelyeknek a megoldása gyorsan ellenőrizhető
P = NP?	Nyitott kérdés, eldöntetlen
Ha P = NP	Forradalmi következmények a tudományban és iparban
Ha P ≠ NP	Sok probléma természetesen nehéz, kriptográfia biztonságos
Jutalom	$1 millió, ha bebizonyítod

---

További információk

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