P versus NP probléma

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.

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.

Ez egyike a Clay Mathematics Institute á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 $2^{2^{cn}}$ 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.

A döntési problémákon kívül más kérdések is mérlegelhetők. Az egyik ilyen, számlálási feladatokból álló osztály a #P elnevezés: míg egy NP probléma azt kérdezi: "Van-e megoldás?", addig a megfelelő #P probléma azt kérdezi, hogy "Hány megoldás létezik?" Nyilvánvaló, hogy a #P feladatnak legalább olyan nehéznek kell lennie, mint a megfelelő NP feladatnak, mivel a megoldások száma azonnal jelzi, hogy létezik-e legalább egy megoldás, ha a szám nagyobb nullánál. Meglepő módon néhány nehéznek vélt #P probléma könnyű (például lineáris idejű) P problémáknak felel meg. Ezekre a problémákra nagyon könnyű megmondani, hogy létezik-e megoldás, de nagyon nehéz megmondani, hogy hány. E problémák közül sok #P-teljes, és ezért a #P legnehezebb problémái közé tartozik, mivel bármelyikük polinomiális idejű megoldása lehetővé tenné az összes többi #P probléma polinomiális idejű megoldását.

Az NP-ben előforduló problémák nem ismertek P-ben vagy NP-ben

1975-ben Richard E. Ladner kimutatta, hogy ha P ≠ NP, akkor NP-ben vannak olyan problémák, amelyek sem P-ben, sem NP-ben nem teljesek. Az ilyen problémákat NP-köztes problémáknak nevezzük. A gráfizomorfizmus problémája, a diszkrét logaritmus probléma és az egészfaktorizációs probléma példák az NP-köztesnek hitt problémákra. Ezek azok a nagyon kevés NP-problémák, amelyekről nem ismert, hogy P-ben vannak, vagy NP-teljesek.

A gráfizomorfizmus probléma annak meghatározásának számítási problémája, hogy két véges gráf izomorf-e. A komplexitáselmélet egyik fontos megoldatlan problémája, hogy a gráfizomorfizmus probléma P-ben van, NP-teljes vagy NP-köztes. A válasz nem ismert, de úgy gondolják, hogy a probléma legalábbis nem NP-teljes. Ha a gráf izomorfizmusa NP-teljes, akkor a polinomiális időhierarchia összeomlik a második szintre. Mivel széles körben elterjedt az a vélemény, hogy a polinomiális hierarchia nem omlik össze semmilyen véges szintre, úgy gondolják, hogy a gráfizomorfizmus nem NP-teljes. Erre a problémára a legjobb algoritmus Babai Lászlónak köszönhetően kvázipolinomiális időben fut.

Az egész számok faktorizációs problémája egy adott egész szám prímtényezői meghatározásának számítási problémája. Döntési problémaként fogalmazva ez annak eldöntésének problémája, hogy a bemenetnek van-e k-nál kisebb tényezője. Nem ismert hatékony egészszám-faktorizációs algoritmus, és ez a tény számos modern kriptográfiai rendszer alapját képezi, mint például az RSA-algoritmus. Az egész számok faktorizációs problémája NP-ben és co-NP-ben (és még UP-ban és co-UP-ban is) van. Ha a probléma NP-teljes, akkor a polinomiális időhierarchia összeomlik az első szinten (azaz NP = co-NP). Az egész számok faktorizálásának leghatékonyabb ismert algoritmusa az általános számmezőszita, amely várható időt vesz igénybe

$O\left(\exp \left(\left({\tfrac {64n}{9}}\log(2)\right)^{\frac {1}{3}}\left(\log(n\log(2))\right)^{\frac {2}{3}}\right)\right)$

egy n bites egész szám faktorálásához. A probléma legismertebb kvantumalgoritmusa, a Shor-algoritmus azonban polinomiális időben fut, bár ez nem jelzi, hol van a probléma a nem kvantum komplexitási osztályok tekintetében.

P jelentése „könnyű”?

A fenti tárgyalások mindegyike azt feltételezi, hogy P jelentése „könnyű”, a „nem P-ben” pedig „nehéz”-et jelent, ez a feltételezés Cobham téziseként ismert. Ez egy általános és meglehetősen pontos feltevés a komplexitáselméletben; azonban van néhány figyelmeztetés.

Először is, ez nem mindig igaz a gyakorlatban. Egy elméleti polinomiális algoritmusnak rendkívül nagy konstans tényezői vagy kitevői lehetnek, ezért nem használható.Például annak eldöntésének problémája, hogy egy G gráf tartalmaz-e H-t minorként, ahol H fix, megoldható O(n²) futási idő alatt, ahol n a G csúcsainak száma. Azonban a nagy O A jelölés egy olyan állandót rejt, amely szuperexponenciálisan függ H-tól. Az állandó nagyobb mint ${\displaystyle 2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (h/2)))}$ (Knuth felfelé mutató nyíl jelölésével), és ahol h a H csúcsainak száma.

Másrészt, még ha egy probléma NP-teljesnek bizonyul is, és még akkor is, ha P ≠ NP, akkor is létezhetnek hatékony megközelítések a probléma gyakorlati kezelésére. Számos NP-teljes problémára létezik olyan algoritmus, mint például a hátizsák-probléma, az utazó ügynök problémája és a Boole-féle kielégítési probléma, amely optimálisan meg tud oldani sok valós esetet észszerű idő alatt. Az ilyen algoritmusok empirikus átlagos eseti összetettsége (idő vs. probléma mérete) meglepően alacsony lehet. Példa erre a lineáris programozás szimplex algoritmusa, amely a gyakorlatban meglepően jól működik; annak ellenére, hogy a legrosszabb eset exponenciális összetettsége van, egyenrangú a legismertebb polinomiális idejű algoritmusokkal.

Végül vannak olyan számítási típusok, amelyek nem felelnek meg a Turing-gép-modellnek, amelyen P és NP van definiálva, ilyen például a kvantumszámítás és a véletlenszerű algoritmusok.

Okok amiért azt lehet hinni, hogy P ≠ NP vagy P = NP

Cook a következőképpen fogalmazza meg a problémát: P = NP ?. A közvélemény-kutatások szerint a legtöbb informatikus úgy véli, hogy P ≠ NP. Ennek a hiedelemnek a fő oka az, hogy a problémák több évtizedes tanulmányozása után senki sem tudott polinomiális idejű algoritmust találni a több mint 3000 fontos ismert NP-teljes probléma egyikére sem (lásd az NP-teljes problémák listáját). Ezeket az algoritmusokat már jóval azelőtt keresték, hogy az NP-teljesség fogalmát egyáltalán meghatározták volna (Karp 21 NP-teljes problémája, az elsők között, mind jól ismert létező problémák voltak, amikor NP-teljesnek bizonyult). Ezenkívül a P = NP eredmény sok más megdöbbentő eredményre utalna, amelyekről jelenleg úgy gondolják, hogy hamisak, például NP = co-NP és P = PH.

Az is intuitív érvelés, hogy a nehezen megoldható, de könnyen ellenőrizhető problémák megléte megfelel a valós tapasztalatnak.

Ha P = NP, akkor a világ merőben más hely lenne, mint ahogy azt általában feltételezzük. Nem lenne különösebb érték a „kreatív ugrásokban”, nincs alapvető szakadék a probléma megoldása és a megoldás felismerése között, ha egyszer megtaláltuk. — Scott Aaronson, UT Austin

Másrészt egyes kutatók úgy vélik, hogy túlzottan bíznak P ≠ NP-ben, és a kutatóknak meg kell vizsgálniuk a P = NP bizonyítékait is. Például 2002-ben ezek a kijelentések hangzottak el:

A fő érv a P ≠ NP mellett az, hogy a kimerítő keresés terén nem történt alapvető előrelépés. Ez véleményem szerint nagyon gyenge érv. Az algoritmusok tere nagyon nagy, feltárásának még csak az elején járunk. [...] Fermat utolsó tételének feloldása is azt mutatja, hogy nagyon egyszerű kérdéseket csak nagyon mély elméletekkel lehet megoldani.

— Moshe Y. Vardi, Rice University

A spekulációhoz való kötődés nem jó útmutató a kutatástervezéshez. Mindig meg kell próbálni minden probléma mindkét irányát. Az előítéletek miatt a híres matematikusok nem tudtak megoldani olyan híres problémákat, amelyek megoldása ellentétes volt várakozásaikkal, noha minden szükséges módszert kidolgoztak.

— Anil Nerode, Cornell University

A megoldás következményei

Az egyik oka annak, hogy a probléma annyira felkelti a figyelmet, a lehetséges válaszok következményei. Bármelyik feloldási irány óriási előrelépést jelentene az elméletben, és talán óriási gyakorlati következményei is lehetnek.

P = NP

Annak bizonyítása, hogy P = NP, lenyűgöző gyakorlati következményekkel járhat, ha a bizonyítás hatékony módszerekhez vezet az NP néhány fontos problémájának megoldására. A lehetséges – pozitív és negatív – következmények is felmerülnek, mivel a különféle NP-teljes problémák sok területen alapvetőek.

Az is nagyon lehetséges, hogy egy bizonyítás nem vezetne gyakorlati algoritmusokhoz NP-teljes problémákra. A feladat megfogalmazása nem igényli, hogy a határoló polinom kicsi, vagy akár konkrétan ismert legyen. A nem konstruktív bizonyítás megmutathatja, hogy egy megoldás létezik anélkül, hogy megadná sem a megszerzéséhez szükséges algoritmust, sem pedig egy konkrét korlátot. Még ha a bizonyítás konstruktív, explicit határoló polinomot és algoritmikus részleteket mutat, ha a polinom nem túl alacsony rendű, az algoritmus a gyakorlatban nem biztos, hogy kellően hatékony. Ebben az esetben a kezdeti bizonyítás elsősorban az elméleti szakembereket érdekelné, de a polinomiális időbeli megoldások lehetségességének ismerete minden bizonnyal jobb (és esetleg gyakorlati) módszerek kutatására sarkallna ezek elérésére.

Példa egy olyan mezőre, amelyet egy P = NP mutató megoldással fel lehet fejleszteni, a kriptográfia, amely arra épül, hogy bizonyos problémák nehezen megoldhatóak. Egy NP-teljes probléma konstruktív és hatékony megoldása, mint például a 3-SAT, megtörné a legtöbb létező kriptorendszert, beleértve:

• A nyilvános kulcsú kriptográfia meglévő megvalósításai, amelyek számos modern biztonsági alkalmazás alapját képezik, mint például a biztonságos internetes pénzügyi tranzakciók.
• Szimmetrikus rejtjelek, például AES vagy 3DES, kommunikációs adatok titkosításához.
• A kriptográfiai hash függvény, amely a blokklánc kriptovaluták, például a bitcoin mögött áll, és a szoftverfrissítések hitelesítésére szolgál. Ezeknél az alkalmazásoknál nehéznek kell lennie egy adott értékhez hasító előkép megtalálásának ahhoz, hogy hasznos legyen, és ideális esetben exponenciális időt igényel. Ha azonban P = NP, akkor az M előkép megtalálása megoldható polinomiális időben, SAT-ra való redukción keresztül.

Ezeket módosítani kell vagy helyettesíteni kell információelméletileg biztonságos megoldásokkal, amelyek nem eredendően a P-NP egyenértékűségen alapulnak.

Másrészt óriási pozitív következményei vannak annak, ha számos matematikailag jelenleg megoldhatatlan probléma kezelhetővé válik. Például az operációkutatásban sok probléma NP-teljes, ilyen például az egész számok programozása és az utazó ügynök problémája. E problémák hatékony megoldása óriási hatással lenne a logisztikára. Sok más fontos probléma, például néhány probléma a fehérjeszerkezet előrejelzésében, szintén NP-teljes; ha ezek a problémák hatékonyan megoldhatók lennének, az jelentős előrelépést ösztönözhet az élettudományok és a biotechnológia területén.

De az ilyen változások jelentősége elhalványulhat ahhoz a forradalomhoz képest, amelyet magában a matematikában okozna egy hatékony módszer az NP-teljes problémák megoldására. Gödel a számítási bonyolultságról szóló korai gondolataiban megjegyezte, hogy egy mechanikus módszer, amely bármilyen problémát megoldana, forradalmasítaná a matematikát:

Ha valóban létezne egy φ(n) ∼ k ⋅ n (vagy akár ∼ k ⋅ n2) gép, ennek a legnagyobb jelentőségű következményei lennének. Ez ugyanis nyilvánvalóan azt jelentené, hogy az Entscheidungs-probléma eldönthetetlensége ellenére a matematikus igen-nem kérdésekre vonatkozó mentális munkáját teljesen helyettesíteni lehetne egy géppel. Hiszen egyszerűen olyan nagynak kellene kiválasztani az n természetes számot, hogy amikor a gép nem ad eredményt, nincs értelme tovább gondolni a problémára.

Hasonlóképpen Stephen Cook (nem csak bizonyítékot, hanem gyakorlatilag hatékony algoritmust feltételezve) azt mondja:

... átalakítaná a matematikát azáltal, hogy lehetővé tenné a számítógép számára, hogy formális bizonyítékot találjon bármely tételre, amelynek észszerű hosszúságú bizonyítéka van, mivel a formális bizonyítások könnyen felismerhetők polinomiális időben. A példaproblémák közé tartozhat az összes CMI-díjjal kapcsolatos probléma.

A kutató matematikusok pályafutásukat azzal töltik, hogy tételeket bizonyítanak, és néhány bizonyítás évtizedekig vagy akár évszázadokig is eltartott a problémák megfogalmazása után – például Fermat utolsó tételének bizonyítása több mint három évszázadba telt. Egy olyan módszer, amely garantáltan megtalálja a tételek bizonyítását, ha létezik „észszerű” méret, lényegében véget vetne ennek a küzdelemnek. Donald Knuth kijelentette, hogy azt hitte, hogy P = NP, de tartózkodóan viszonyul egy lehetséges bizonyíték hatásához:

Ha elképzelünk egy véges, de hihetetlenül nagy M számot – például a 10↑↑↑↑3 számot, amelyet a „Végességgel való megküzdés” című írásomban tárgyaltunk –, akkor óriási számú lehetséges algoritmus létezik, amelyek n^M bitenkénti teljesítményt hajtanak végre, vagy összeadás vagy eltolás műveleteket n adott biten, és nagyon nehéz elhinni, hogy ezek az algoritmusok mindegyike meghibásodik. A lényeg azonban az, hogy nem hiszem, hogy a P = NP egyenlőség bizonyítás esetén is hasznos lenne, mert egy ilyen bizonyítás szinte biztosan nem konstruktív.

P ≠ NP

Egy olyan bizonyíték, amely azt mutatja, hogy P ≠ NP, hiányozna a P = NP bizonyításának gyakorlati számítási előnyeiből, de ennek ellenére nagyon jelentős előrelépést jelentene a számítási komplexitás elméletében, és útmutatást adna a jövőbeli kutatásokhoz. Lehetővé tenné annak formális bemutatását, hogy sok gyakori probléma nem oldható meg hatékonyan, így a kutatók figyelme részmegoldásokra vagy más problémák megoldására irányulhat. A P ≠ NP-ben való széles körben elterjedt hiedelem miatt a kutatás e fókuszálásának nagy része már megtörtént.

Szintén P ≠ NP továbbra is nyitva hagyja az NP nehéz problémáinak átlagos eseti összetettségét. Például lehetséges, hogy a SAT a legrosszabb esetben exponenciális időt igényel, de szinte minden véletlenszerűen kiválasztott példánya hatékonyan megoldható. Russell Impagliazzo öt hipotetikus „világot” írt le, amelyek az átlagos eset bonyolultsági kérdésének eltérő lehetséges megoldásaiból adódhatnak. Ezek az "Algorithmica"-tól, ahol P = NP, és az olyan problémák, mint a SAT minden esetben hatékonyan megoldhatók, a "Cryptomania"-ig terjednek, ahol P ≠ NP, és könnyű P-n kívüli nehéz problémák generálása, három köztes lehetőséggel, amelyek különböző lehetségeseket tükröznek. a nehézségek eloszlása az NP-nehéz problémák esetei között. Azt a „világot”, ahol P ≠ NP, de átlagos esetben minden NP-beli probléma kezelhető, a cikkben „Heuristica”-nak nevezik. A Princeton Egyetem 2009-es műhelye az öt világ helyzetét tanulmányozta.

A bizonyítás nehézségére vonatkozó eredmények

Bár maga a P = NP probléma a millió dolláros nyeremény és a rengeteg elkötelezett kutatás ellenére nyitott marad, a probléma megoldására tett erőfeszítések számos új technikához vezettek. A P = NP problémával kapcsolatos legtermékenyebb kutatások közül néhány annak kimutatása volt, hogy a meglévő bizonyítási technikák nem elég erősek a kérdés megválaszolásához, ami azt sugallja, hogy új technikai megközelítésekre van szükség.

A probléma nehézségének további bizonyítékaként a számítási komplexitáselméletben lényegében az összes ismert bizonyítási technika a következő osztályozások valamelyikébe tartozik, amelyekről ismert, hogy mindegyik nem elegendő annak bizonyítására, hogy P ≠ NP:

Osztályozás	Meghatározás
A bizonyítások relativizálása	Képzelj el egy olyan világot, ahol minden algoritmus lekérdezhet valamilyen rögzített szubrutinról, amelyet orákulumnak neveznek (egy fekete doboz, amely állandó idő alatt tud válaszolni egy rögzített kérdéscsoportra, például egy fekete doboz, amely egy adott utazó ügynök problémáját egy lépésben megoldja), és az orákulum futási idejét nem számítják bele az algoritmus futási idejébe. A legtöbb bizonyítás (különösen a klasszikus) egységesen érvényes az orákulumokkal rendelkező világban, függetlenül attól, hogy az orákulum mit csinál. Ezeket a bizonyításokat relativizálásnak nevezzük. 1975-ben Baker, Gill és Solovay kimutatta, hogy P = NP egyes orákulumok esetében, míg P ≠ NP más orákulumok esetében. Mivel a relativizáló bizonyítások csak olyan állításokat tudnak bizonyítani, amelyek minden lehetséges jóslatra egységesen igazak, ez azt mutatta, hogy a relativizáló technikák nem tudják feloldani a P = NP-t.
Természetes bizonyítékok	1993-ban Alexander Razborov és Steven Rudich meghatározta a bizonyítási technikák általános osztályát az áramkörök bonyolultságának alsó határaira, amelyeket természetes bizonyításoknak neveznek. Abban az időben az összes korábban ismert áramkör alsó határa természetes volt, és az áramkör bonyolultságát nagyon ígéretes megközelítésnek tekintették a P = NP feloldására. Razborov és Rudich azonban megmutatta, hogy ha léteznek egyirányú függvények, akkor egyetlen természetes bizonyítási módszer sem tud különbséget tenni P és NP között. Bár az egyirányú függvények létezését formálisan soha nem bizonyították, a legtöbb matematikus úgy gondolja, hogy igen, és létezésük bizonyítéka sokkal erősebb állítás lenne, mint a P ≠ NP. Így nem valószínű, hogy a természetes bizonyítások önmagukban feloldják a P = NP-t.
Algebrizáló bizonyítások	A Baker–Gill–Solovay-eredmény után új, nem relativizáló bizonyítási technikákat alkalmaztak sikeresen annak bizonyítására, hogy IP = PSPACE. 2008-ban azonban Scott Aaronson és Avi Wigderson kimutatta, hogy az IP = PSPACE bizonyításban használt fő technikai eszköz, az úgynevezett aritmetizálás, szintén nem volt elegendő a P = NP feloldásához.

Ezek az akadályok egy másik ok, amiért az NP-teljes feladatok hasznosak: ha egy polinomiális idejű algoritmus demonstrálható egy NP-teljes feladatra, az megoldaná a P = NP problémát a fenti eredmények által nem kizárt módon.

Ezek az akadályok arra is késztettek néhány informatikust, hogy azt sugallják, a P versus NP probléma független lehet az olyan szabványos axiómarendszerektől, mint a ZFC (azokon belül nem bizonyítható vagy cáfolható). Egy függetlenségi eredmény értelmezése lehet az, hogy vagy nem létezik polinomiális idejű algoritmus egyetlen NP-teljes feladatra sem, és ilyen bizonyítást nem lehet megszerkeszteni (pl.) ZFC-ben, vagy létezhetnek polinom idejű algoritmusok NP-teljes problémákra, de a ZFC-ben lehetetlen bizonyítani, hogy az ilyen algoritmusok helyesek. Ha azonban a jelenleg alkalmazható technikákkal kimutatható, hogy a probléma még sokkal gyengébb, a Peano-axiómákat (PA) egész számokra kiterjesztett feltevésekkel sem eldönthető, akkor szükségszerűen létezne kb. polinomiális idejű algoritmusok az NP minden problémájához. Ezért, ha valaki azt hiszi (ahogy a legtöbb komplexitáselmélet képviselője), hogy az NP-ben nem minden problémának van hatékony algoritmusa, abból az következne, hogy a függetlenség bizonyítása ezekkel a technikákkal nem lehetséges. Ezen túlmenően ez az eredmény arra utal, hogy a PA-tól vagy ZFC-től való függetlenség bizonyítása jelenleg ismert technikákkal nem egyszerűbb, mint az NP összes problémájára hatékony algoritmusok létezésének bizonyítása.

Állított megoldások

Míg a P versus NP problémát általában megoldatlannak tekintik, sok amatőr és néhány profi kutató keresett megoldást. Gerhard J. Woeginger egy listát tart fenn, amely 2016-ban 62 P = NP állítólagos bizonyítását, 50 P ≠ NP bizonyítását tartalmazza, 2 bizonyítékot, hogy a probléma nem igazolható, és egy bizonyítékot arra, hogy eldönthetetlen. A P versus NP feloldására tett néhány kísérlet rövid médiafigyelmet kapott, bár ezeket a próbálkozásokat azóta megcáfolták.

Logikai jellemzések

A P = NP probléma a leíró komplexitásban végzett munka eredményeként a logikai állítások bizonyos osztályaival is megfogalmazható.

Tekintsük az összes olyan véges szerkezetű nyelvet, amely rögzített aláírással rendelkezik, beleértve a lineáris sorrendű relációt. Ezután az összes ilyen P-beli nyelv kifejezhető elsőrendű logikával egy megfelelő legkisebb fixpontos kombinátor hozzáadásával. Ez gyakorlatilag a sorrenddel kombinálva lehetővé teszi a rekurzív függvények meghatározását. Mindaddig, amíg az aláírás a megkülönböztetett sorrendi reláción kívül legalább egy predikátumot vagy függvényt tartalmaz, tehát az ilyen véges struktúrák tárolására felhasznált hely ténylegesen polinomiális a szerkezet elemeinek számában, ez pontosan jellemzi P-t.

Hasonlóképpen, az NP az egzisztenciális másodrendű logikában kifejezhető nyelvek halmaza – vagyis olyan másodrendű logikában, amely a relációk, függvények és részhalmazok egyetemes kvantifikációjának kizárására korlátozódik. A PH polinomi hierarchiában szereplő nyelvek az egész másodrendű logikának felelnek meg. Így a „P megfelelő részhalmaza-e az NP-nek” kérdés újrafogalmazható úgy, hogy „képes-e az egzisztenciális másodrendű logika olyan nyelveket leírni (véges, lineárisan rendezett struktúrákból, amelyek nem triviális aláírással rendelkeznek), amelyeket a legkevésbé fixpontos elsőrendű logika nem tud?” . Az "egzisztenciális" szót akár ki is hagyhatjuk az előző jellemzésből, mivel P = NP akkor és csak akkor, ha P = PH (mivel az előbbi azt állapítaná meg, hogy NP = co-NP, ami viszont azt jelenti, hogy NP = PH).

Polinom-idő algoritmusok

Egyetlen NP-teljes feladathoz sem ismert olyan algoritmus, amely polinomiális időben futna. Vannak azonban olyan algoritmusok, amelyek ismertek NP-teljes problémákra azzal a tulajdonsággal, hogy ha P = NP, akkor az algoritmus polinomiális időben fut az elfogadó példányokon (bár hatalmas állandókkal, így az algoritmus nem praktikus). Ezek az algoritmusok azonban nem minősülnek polinomiális időnek, mivel futási idejük az elutasító példányokon nem polinomiális. A következő algoritmus, Levinnek köszönhetően (minden idézet nélkül), egy ilyen példa az alábbiakban. Helyesen elfogadja a SUBSET-SUM NP-teljes nyelvet. Polinomiális időben fut olyan bemeneteken, amelyek a SUBSET-SUM-ban vannak, akkor és csak akkor, ha P = NP:

// Algoritmus, amely elfogadja a SUBSET-SUM NP-teljes nyelvet.
//
// ez egy polinomiális idejű algoritmus akkor és csak akkor, ha P = NP.
//
// A „polinomidő” azt jelenti, hogy „igen”-t ad vissza polinomidőben, amikor
// a válasz „igen” legyen, és örökké tart, ha „nem”.
//
// Bemenet: S = egész számok véges halmaza
// Kimenet: "igen", ha az S bármely részhalmaza 0-t tesz ki.
// Örökké fut, különben nincs kimenet.
// Megjegyzés: Az "M programszám" az a program, amelyet úgy kapunk,
// hogy az M egész számot binárisan írjuk, majd ezt a bitsort
// programnak tekintjük.
// Minden lehetséges program előállítható így,
// bár a legtöbb nem tesz semmit 
// a szintaktikai hibák miatt.
FOR K = 1...∞
  FOR M = 1...K
    Futtassa az M számú programot K lépésre az S bemenettel
    HA a program különálló egész számok listáját adja ki
      ÉS az egész számok mind S-ben vannak
      ÉS az egész számok összege 0
    AKKOR
      KIMENET "igen" és ÁLLJ

Akkor és csak akkor, ha P = NP, akkor ez egy polinomiális idejű algoritmus, amely elfogad egy NP-teljes nyelvet. Az „elfogadás” azt jelenti, hogy „igen” választ ad polinomiális időben, de örökké futhat, ha a válasz „nem” (más néven félalgoritmus).

Ez az algoritmus rendkívül nem praktikus, még akkor is, ha P = NP. Ha a legrövidebb program, amely polinomiális idő alatt képes megoldani a SUBSET-SUM-ot, b bit hosszú, akkor a fenti algoritmus először legalább 2^b − 1 másik programmal próbálkozik.

Formális definíciók

P és NP

Fogalmi értelemben a döntési probléma olyan probléma, amely valamilyen w karakterláncot vesz be egy Σ ábécé fölé, és "igen" vagy "nem"-et ad ki. Ha van olyan algoritmus (mondjuk egy Turing-gép, vagy egy korlátlan memóriájú számítógépes program), amely bármely n hosszúságú bemeneti karakterláncra legfeljebb cn^k lépésben képes a helyes választ adni, ahol k és c a bemeneti karakterlánctól független állandók, akkor azt mondjuk, hogy a feladat polinomiális időben megoldható, és a P osztályba helyezzük. Formálisan P az összes olyan nyelv halmaza, amelyet egy determinisztikus polinom-idő Turing-gép eldönthet. vagyis

$\mathbf {P} =\{L:L=L(M){\text{ valamilyen determinisztikus polinomiális idejű Turing-gépre }}M\}$

ahol

$L(M)=\{w\in \Sigma ^{*}:M{\text{ elfogadja }}w\}$

és egy determinisztikus polinomiális idejű Turing-gép egy M determinisztikus Turing-gép, amely teljesíti a következő két feltételt:

1. M leáll minden w és bemeneten
2. létezik $k\in N$ így a $T_{M}(n)\in O(n^{k})$ ahol O a nagy O jelölésre és

$T_{M}(n)=\max\{t_{M}(w):w\in \Sigma ^{*},|w|=n\}$ $t_{M}(w)={\text{ lépések száma }}M{\text{ bevitelkor leáll }}w.$

Az NP hasonló módon definiálható nemdeterminisztikus Turing-gépekkel (a hagyományos módon). Az NP meghatározásának modern megközelítése azonban a tanúsítvány és a hitelesítő fogalmának használata. Formálisan az NP azon nyelvek halmaza egy véges ábécén keresztül, amelyek polinomiális időben futó ellenőrzővel rendelkeznek, ahol az "ellenőrző" fogalmát a következőképpen határozzuk meg.

Legyen L nyelv egy véges ábécé felett, Σ.

L ∈ NP akkor és csak akkor, ha létezik bináris reláció $R\subset \Sigma ^{*}\times \Sigma ^{*}$ és egy k pozitív egész szám úgy, hogy a következő két feltétel teljesül:

1. Minden $x\in \Sigma ^{*}$$x\in L\Leftrightarrow \exists y\in \Sigma ^{*}$ esetén az (x, y) ∈ R és $|y|\in O(|x|^{k})$; és
2. a nyelv $L_{R}=\{x\#y:(x,y)\in R\}$ felett $\Sigma \cup \{\#\}$ egy determinisztikus Turing-géppel polinomiális időben eldönthető.

Az L_R eldöntő Turing-gépet L és a y ellenőrzőjének nevezzük úgy, hogy (x, y) ∈ R az x L-beli tagsági bizonyítványának nevezzük.

Általánosságban elmondható, hogy a hitelesítőnek nem kell polinomiális idejűnek lennie. Ahhoz azonban, hogy L NP-ben legyen, rendelkeznie kell egy polinomiális időben lefutó ellenőrzővel.

Példa

${\displaystyle \mathrm {COMPOSITE} =\left\{x\in \mathbb {N} \mid x=pq{\text{ egész számokhoz }}p,q>1\right\}}$ ${\displaystyle R=\left\{(x,y)\in \mathbb {N} \times \mathbb {N} \mid 1<y\leq {\sqrt {x}}{\text{ és }}y{\text{ osztva }}x\right\}.}$

Nyilvánvaló, hogy az a kérdés, hogy egy adott x összetett-e, egyenértékű azzal a kérdéssel, hogy x tagja-e az ÖSSZETETTnek. Megmutatható, hogy KOMPOZIT ∈ NP, ha ellenőrizzük, hogy megfelel-e a fenti definíciónak (ha a természetes számokat bináris reprezentációikkal azonosítjuk).

A KOMPOZIT történetesen P-ben is megtalálható, ezt a tényt az AKS primalitásteszt feltalálása bizonyítja.

NP-teljesség

Az NP-teljesség leírásának sok egyenértékű módja létezik.

Legyen L nyelv egy Σ véges ábécé felett.

L akkor és csak akkor NP-teljes, ha a következő két feltétel teljesül:

1. L ∈ NP; és
2. Bármely L az NP-ben polinomiális időre redukálható L-re (írva: $L'\leq _{p}L$), ahol $L'\leq _{p}L$ akkor és csak akkor, ha a következő két feltétel teljesül:
   1. Létezik f : Σ* → Σ* úgy, hogy a Σ*-ban szereplő összes w esetén a következő:$(w\in L'\Leftrightarrow f(w)\in L)$; és
   2. létezik egy polinomiális idejű Turing-gép, amely f(w)-vel megáll a szalagján bármely w bemeneten.

Alternatív megoldásként, ha L ∈ NP, és van egy másik NP-teljes probléma, amely polinomidőben L-re redukálható, akkor L NP-teljes. Ez egy gyakori módszer annak bizonyítására, hogy néhány új probléma NP-teljes.

A populáris kultúrában

• Timothy Lanzone rendező Travelling Salesman (Utazó kereskedő) című filmje négy matematikus története, akiket az Egyesült Államok kormánya bérelt fel a P versus NP probléma megoldására.
• A Simpson család hetedik évadának Treehouse of Horror hatodik epizódjában a P = NP egyenlet nem sokkal azután látható, hogy Homer véletlenül belebotlott a „harmadik dimenzióba”.
• Az Elementary tévésorozat 2. évadának második epizódjában ("Solve for X") Sherlock és Watson olyan matematikusok gyilkosságait vizsgálják, akik megpróbálták megoldani a P-t és az NP-t.

Kapcsolódó szócikk

• A matematika megoldatlan problémáinak listája