Szerkesztő:Laci15/próbalap
P versus NP probléma[szerkesztés]
A Wikipédiából, a szabad enciklopédiából
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, exponenciális idő). 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 megoldhatók-e polinomiális időben is. Ha kiderül, hogy P ≠ NP, az azt jelentené, hogy az NP-ben vannak olyan problémák, amelyeket nehezebb kiszámítani, mint ellenőrizni: ezeket nem lehet polinom időben megoldani, de a válasz igazolható polinom időben .
A problémát sokan a számítástechnika legfontosabb nyitott problémájának tartják.[1] 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.[2]
Ez egyike a Clay Mathematics Institute által kiválasztott hét Millenniumi Díj-probléma közül, amelyek mindegyike US$1 000 000-os díjat kap az első helyes megoldásért.
Példa[szerkesztés]
Tekintsük példának a Sudoku-t, 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ű Sudoku rá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 Sudoku 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[szerkesztés]
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 összetett kód feltöréséhez exponenciális időre lesz szükség a kulcs hosszában. 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[szerkeszté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 a számítógép modelljére, amelyhez időt kell elemezni. 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 nem-determinisztikus 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 célszerű lenni. számoljon be a korszak szubjektív véleményéről.″
NP-teljesség[szerkesztés]
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 Sudoku játékot is. Ebben az esetben a bizonyítás azt mutatja, hogy a Sudoku 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 Sudoku 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[szerkesztés]
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.
- ↑ Fortnow, Lance (2009). "The status of the P versus NP problem"
- ↑ Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.