A P versus NP probléma a számítástechnika egyik legnagyobb megoldatlan problémája. Azt kérdezi és arra keresi a választ, hogy minden olyan probléma, amelynek megoldása gyorsan ellenőrizhető, az gyorsan megoldható-e.
A fentiekben használt informális gyors kifejezés azt jelenti, hogy létezik egy olyan algoritmus, amely megoldja a feladatot, és amely polinomiális időben fut, így a feladat végrehajtásának ideje polinomiális függvényként változik az algoritmus bemenetének nagyságától függően (ellentétben mondjuk, az exponenciális idővel). A kérdések azon általános osztálya, amelyre valamilyen algoritmus polinomiális időben választ tud adni, az a "P" vagy a "P osztály". Egyes kérdésekre nincs ismert mód a gyors válasz megtalálására, de ha olyan információkkal látjuk el, amelyek megmutatják, mi a válasz, akkor gyorsabban ellenőrizhető és megtalálható a válasz. Azon kérdések osztálya, amelyekre a válasz igazolható polinomiális időben, az NP, ami a „nemdeterminisztikus polinomidő” rövidítése.Egy nemdeterminisztikus Turing-gép olyan állapotba léphet, amelyet nem határoz meg az előző állapot. Egy ilyen gép meg tud oldani egy NP-feladatot polinomiális időben úgy, hogy (szerencsére) a helyes válasz állapotába kerül, majd konvencionálisan ellenőrzi azt. Az ilyen gépek nem alkalmasak reális problémák megoldására, de elméleti modellként használhatók.
A P versus NP kérdésre adott válasz meghatározná, hogy a polinomiális időben igazolható problémák meg is oldhatók polinomiális időben. Ha kiderül, hogy P ≠ NP, az azt jelentené, hogy az NP-ben vannak olyan problémák, amelyeket nehezebb megoldani, mint ellenőrizni: ezeket nem lehet polinomiális időben megoldani, de a válasz igazolható polinomiális időben.
A problémát sokan a számítástechnika legfontosabb nyitott problémájának tartják. Amellett, hogy a számításelmélet egyik fontos problémája, a bizonyítás mindkét irányban mélyreható következményekkel járna a matematikára, a kriptográfiára, az algoritmuskutatásra, a mesterséges intelligenciára, a játékelméletre, a multimédiás feldolgozásra, a filozófiára, a közgazdaságtanra és sok más területre.Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
Ez egyike a Clay Matematikai Intézet által kiválasztott hét Millenniumi Díj-probléma közül, amelyek mindegyike 1 000 000 dolláros díjat kap az első helyes megoldásért.
Példa Tekintsük példának a szúdokut, egy olyan játékot, ahol a játékos egy részben kitöltött számrácsot kap, és bizonyos szabályok betartásával megpróbálja kitölteni a rácsot. Adott egy hiányos, bármilyen méretű szúdokurács, létezik legalább egy valódi tényleges megoldás? Bármely javasolt megoldás könnyen ellenőrizhető, és a megoldás ellenőrzésének ideje lassan (polinomiálisan) nő, ahogy a rács egyre nagyobb lesz. Azonban a megoldások megtalálására szolgáló összes ismert algoritmus – a nehéz példák esetében – időbe telik, ami exponenciálisan növekszik, ahogy a rács egyre nagyobb lesz. Tehát a szúdoku NP-ben van (gyorsan ellenőrizhető), de úgy tűnik, hogy nem P-ben (gyorsan megoldható). Több ezer más probléma hasonlónak tűnik, mivel gyorsan ellenőrizhető, de lassú a megoldása. A kutatók kimutatták, hogy az NP számos problémája rendelkezik azzal az extra tulajdonsággal, hogy bármelyikük gyors megoldása felhasználható az NP bármely más problémájának gyors megoldására, ezt a tulajdonságot NP-teljességnek nevezik. Több évtizedes kutatás nem hozott gyors megoldást e problémák egyikére sem, ezért a legtöbb tudós azt gyanítja, hogy e problémák egyike sem oldható meg gyorsan. Ezt azonban soha nem sikerült bebizonyítani.
Történet A P versus NP probléma pontos megállapítását 1971-ben Stephen Cook vezette be A tételbizonyítási eljárások bonyolultsága című alapművében (és ettől függetlenül Leonid Levin 1973-ban).
Bár a P versus NP problémát formálisan 1971-ben határozták meg, voltak korábbi sejtések a felmerülő problémákról, a bizonyítás nehézségeiről és a lehetséges következményekről. 1955-ben John Nash matematikus levelet írt az NSA-nak, amelyben azt feltételezte, hogy egy kellően bonyolult kód feltöréséhez a kulcs hosszával exponenciálisan arányos időre lenne szükség. Ha bebizonyosodik (és Nash kellően szkeptikus volt), ez azt jelentené, amit ma P ≠ NP-nek neveznek, mivel a javasolt kulcs könnyen ellenőrizhető polinomiális időben. A mögöttes probléma másik említése Kurt Gödel 1956-os levelében történt Neumann Jánosnak. Gödel feltette a kérdést, hogy a tételbizonyítás (ma ismert, hogy co-NP-teljes) megoldható-e másodfokú vagy lineáris időben, és rámutatott az egyik legfontosabb következményre, hogy ha igen, akkor a matematikai bizonyítások feltárása automatizálható.
Összefüggés A P és NP komplexitási osztályok közötti kapcsolatot a számítási komplexitáselmélet, a számításelmélet azon része vizsgálja, amely az adott probléma megoldásához szükséges számítási erőforrásokkal foglalkozik. A leggyakoribb erőforrások az idő (hány lépés szükséges egy probléma megoldásához) és a tér (mennyi memória szükséges egy probléma megoldásához).
Az ilyen elemzéshez szükség van annak a számítógépnek a modelljére, amelynek az idejét elemezni kell. Az ilyen modellek általában azt feltételezik, hogy a számítógép determinisztikus (a számítógép jelenlegi állapotát és az esetleges bemeneteket figyelembe véve csak egy lehetséges műveletet hajthat végre) és szekvenciális (egymás után hajtja végre a műveleteket).
Ebben az elméletben a P osztály mindazon döntési problémákat tartalmazza (lásd alább), amelyek egy determinisztikus szekvenciális gépen a bemenet méretét tekintve polinomiális idő alatt megoldhatók; az NP osztály mindazokból a döntési problémákból áll, amelyek pozitív megoldása megfelelő információ mellett polinomiális időben igazolható, vagy ezzel egyenértékű, amelyek megoldása polinomiális időben is megtalálható egy nemdeterminisztikus gépen. Nyilvánvaló, hogy P ⊆ NP. Vitathatatlan, hogy az elméleti számítástechnika legnagyobb nyitott kérdése e két osztály közötti kapcsolatra vonatkozik:
P egyenlő NP-vel?
2002 óta William Gasarch három közvélemény-kutatást végzett kutatók körében ezzel és a kapcsolódó kérdésekkel kapcsolatban. Növekszik az a bizalom, hogy P ≠ NP – 2019-ben 88%-uk hitt P ≠ NP-nek, szemben a 2012-es 83%-kal és a 2002-es 61%-kal. Szakértőkre korlátozva a 2019-es válaszok 99%-a azt hitte, hogy P ≠ NP. Ezek a közvélemény-kutatások nem mondanak semmit arról, hogy a P=NP igaz-e, ahogyan azt maga Gasarch is kijelentette: ″Ez nem visz közelebb a P=?NP megoldásához, vagy ahhoz, hogy tudjuk, mikor lesz megoldva, de megpróbál objektív beszámolót adni a korszak szubjektív véleményéről.″
NP-teljesség
A P = NP kérdés megvitatására az NP-teljesség fogalma nagyon hasznos. Az NP-teljes feladatok olyan feladatok halmaza, amelyek mindegyikére bármely más NP-probléma redukálható polinomiális időben, és amelyek megoldása polinomiális időben még igazolható. Vagyis bármely NP probléma átalakítható bármelyik NP-teljes problémává. Informálisan az NP-teljes probléma egy NP probléma, amely legalább olyan "kemény", mint bármely más probléma az NP-ben.
Az NP-nehéz problémák legalább olyan nehezek és kemények, mint az NP problémák; azaz minden NP probléma redukálható (polinomiális időben) rájuk. Az NP-nehéz problémáknak nem kell az NP-ben lenniük; azaz nem kell, hogy polinomiális időben ellenőrizhető megoldásaik legyenek.
Például a Boole-féle kielégítési probléma NP-teljes a Cook–Levin-tétellel, így az NP-ben szereplő bármely probléma bármely példánya mechanikusan átalakítható a Boole-féle kielégítési probléma polinomiális időbeli példányává. A logikai kielégítési probléma egyike a sok ilyen NP-teljes probléma közül. Ha bármely NP-teljes probléma P-ben van, akkor abból az következne, hogy P = NP. Számos fontos probléma azonban NP-teljesnek bizonyult, és egyikre sem ismert gyors algoritmus.
Önmagában a definíció alapján nem nyilvánvaló, hogy léteznek NP-teljes problémák; azonban egy triviális és kitalált NP-teljes probléma megfogalmazható a következőképpen: ha egy M Turing-gép leírása garantáltan megáll a polinomiális időben, létezik-e olyan polinom méretű bemenet, amelyet M elfogad? NP-ben van, mert (adott bemenet) egyszerűen ellenőrizhető, hogy M elfogadja-e a bemenetet M szimulálásával; NP-teljes, mert az NP-ben lévő probléma bármely konkrét példányának ellenőrzője M polinomiális időgépként kódolható, amely az ellenőrizendő megoldást veszi be bemenetként. Ezután azt a kérdést, hogy a példány igen vagy nem példány-e, az határozza meg, hogy létezik-e érvényes bemenet.
Az első természetes probléma, amely NP-teljesnek bizonyult, a Boole-féle kielégítési probléma, más néven SAT volt. Mint fentebb megjegyeztük, ez a Cook–Levin-tétel; annak bizonyítéka, hogy a kielégíthetőség NP-teljes, technikai részleteket tartalmaz a Turing-gépekről, mivel azok az NP definíciójához kapcsolódnak. Miután azonban bebizonyosodott, hogy ez a probléma NP-teljes, a redukciós bizonyítás egyszerűbb módot adott annak kimutatására, hogy sok más probléma is NP-teljes, beleértve a korábban tárgyalt szúdokujátékot is. Ebben az esetben a bizonyítás azt mutatja, hogy a szúdoku polinomiális idejű megoldása felhasználható latin négyzetek polinomiális időben történő kitöltésére is. Ez viszont megoldást ad a háromrészes gráfok háromszögekre történő particionálására, amelyek segítségével megoldást találhatunk a SAT 3-SAT néven ismert speciális esetére, amely megoldást nyújt az általános logikai kielégíthetőségre. Tehát a szúdoku polinomiális idejű megoldása mechanikai transzformációk sorozatával a kielégíthetőség polinomiális idejű megoldásához vezet, amely viszont felhasználható bármilyen más NP probléma megoldására polinomiális időben. Az ehhez hasonló átalakításokat alkalmazva a látszólag független problémák hatalmas csoportja redukálható egymásra, és bizonyos értelemben „ugyanaz a probléma”.
Nehezebb problémák Bár nem ismert, hogy P = NP, a P-n kívüli problémák ismertek. Ahogy a P osztály polinomiális futási idővel van definiálva, az EXPTIME osztály az összes olyan döntési probléma halmaza, amelynek exponenciális futási ideje van. Más szóval, az EXPTIME bármely problémája megoldható egy determinisztikus Turing-géppel O(2p(n)) időben, ahol p(n) n polinomiális függvénye. Egy döntési probléma EXPTIME-teljes, ha EXPTIME-ben van, és minden EXPTIME-beli feladatnak polinomiális idejű többszörös redukciója van. Számos probléma ismert, hogy EXPTIME-teljes. Mivel kimutatható, hogy P ≠ EXPTIME, ezek a problémák P-n kívül esnek, így több mint polinomidőt igényelnek. Valójában az időhierarchia tétele szerint nem oldhatók meg lényegesen rövidebb idő alatt, mint az exponenciális. A példák közé tartozik a tökéletes stratégia megtalálása sakkpozíciókhoz egy N × N táblán, és hasonló problémák más társasjátékokhoz.
A Presburger-aritmetikában egy állítás igazságának eldöntése még több időt igényel. Fischer és Rabin 1974-ben bebizonyította, hogy minden olyan algoritmus, amely eldönti az n hosszúságú Presburger-állítások igazságát, legalább futásidejű bizonyos c konstans esetén. Emiatt a probléma miatt több mint exponenciális futási időt igényel. Még nehezebbek az eldönthetetlen problémák, mint például a megállási probléma. Ezeket nem lehet teljesen megoldani egyetlen algoritmussal sem, abban az értelemben, hogy minden algoritmushoz van legalább egy olyan bemenet, amelyre az algoritmus nem adja meg a megfelelő választ; vagy rossz választ ad, vagy befejezi anélkül, hogy meggyőző választ adna, vagy egyébként örökké fut anélkül, hogy egyáltalán választ adna.