ellenőrzés könnyebb, mint megtalálni?
a probléma megoldásának megtalálása nehezebb, mint annak ellenőrzése, hogy a megoldás helyes-e. Ez nyilvánvalónak tűnik, ha valaha is megoldott egy Sudoku puzzle-t, vagy megoldott egy Rubik kockát, vagy sakkozott. De ez a kijelentés, bármennyire intuitív megjelenésű, közvetlenül a civilizációnk egyik legmélyebb matematikai kérdéséhez vezet.
a nem determinisztikus polinom idő (vagy NP) problémák azok, ahol könnyen ellenőrizheti a választ, hogy helyes legyen., Ezzel szemben a polinom idő (vagy P) problémák azok a
, ahol a válasz megtalálása egyszerű. Ha megtalálja a választ, akkor ellenőrizte, hogy helyes-e, így a P minden problémája NP-ben is megtalálható. Azt mondjuk, hogy a P az NP alosztálya. Nem tudjuk azonban, hogy van-e olyan probléma az NP-ben, amely nem a P-ben van, és ezt hívjuk P vs NP problémának.
A P vs NP probléma a matematika és az elméleti számítástechnika egyik legfontosabb megoldatlan problémája. Van még egy agyag Millenniumi díj, amely egymillió dollárt kínál a megoldásért., Azonban valószínűleg sokkal könnyebb módja annak, hogy milliomos legyen, mint a P vs NP megoldása!
volt egy zümmögés a közelmúltban, amikor valaki azt állította, hogy megoldja az arXiv-en, bár a bizonyítékban gyorsan találtak egy rést. Tekintettel arra, hogy a probléma iránt a közelmúltban érdeklődés mutatkozott, és központi helyet foglal el a matematikában, ezt a heti blogban tárgyalom.
Sudoku
Ha egy újságban kitöltött Sudoku puzzle-t kap, akkor a kukába dobhatja. De ha akarod, átnézheted a sorokat, oszlopokat és 3 x 3 cellát, hogy elmondd, hogy ez egy érvényes megoldás: az 1, 2, … , 9 mindegyikének pontosan egyszer kell megtörténnie., Ez hasonló az NP-hez, mivel viszonylag könnyű ellenőrizni, hogy a megoldás helyes-e.
Ha azonban részben kitöltött Sudoku puzzle-t adok neked, nehéz lehet megtalálni a megoldást. Ez az öröm és kihívás ez a fajta puzzle. Tehát, hogy az NP nem azonnal úgy tűnik, hogy azt jelenti, a probléma egy könnyű megoldást találni. Ez az intuíció a P vs NP probléma középpontjában áll.
pontos megfogalmazás
A P és az NP pontosabb megértéséhez jobban meg kell értenünk az algoritmusokat és mérnünk a sebességüket. Problémák merülnek fel néhány fix bemenet, kimenet vagy igen vagy nem. A bemenet egy adott hosszúság, mondjuk n, ahol n pozitív egész szám. Ez azt jelenti, hogy hány bit szükséges a bemenet kifejezéséhez. Az algoritmus egy módszer vagy eljárás a probléma megoldására. Az algoritmusok a számítás minden lépésénél utasításokat adnak, és ennek véget kell vetni., A lépések lehetnek másodpercek, ezredmásodpercek vagy más rögzített időintervallum, amely a problémától függ.
a probléma összetettsége a legkisebb legrosszabb esetben futási idő az összes lehetséges algoritmuson keresztül, amely a problémát a bemenet hosszának függvényében oldja meg. Más szavakkal, méri, hogy mennyi ideig tart a probléma megoldása a leggyorsabb algoritmussal,de a legrosszabb esetben.
a probléma polinom időben megoldható, ha n hosszúságú bemenetet adunk meg, annak összetettségét az nm polinom függvény határolja néhány nem negatív egész m-re., A polinom időben megoldható összes probléma halmazát P.
jelöli, nem feltétlenül jelenti azt, hogy a probléma megvalósítható. Például, ha az algoritmus futtatásához n1000 lépésekre van szükség, akkor reménytelenül lassú lesz még a kis N esetében is. a nem determinisztikus polinom (vagy NP) problémák azok, ahol ellenőrizheti, hogy az igen válasz helyes-e polinom időben.
NP-keménység
a probléma NP-nehéz, ha egy polinom-idő algoritmus azt jelentené, polinom-idő algoritmus minden probléma NP. Ezért, ha EGY NP-kemény probléma P-ben volt, akkor P = NP., Az NP-kemény problémák legalább olyan kemények, mint bármely probléma az NP-ben. Egy NP-teljes probléma az, ami NP-kemény és NP.
a klasszikus NP-teljes probléma a Hamilton-ciklus megtalálása. Ehhez tegyük fel, hogy van egy városok hálózata, amelyet utak kötnek össze. A probléma az, hogy minden várost utakkal látogassanak meg (repülőgépek nem engedélyezettek!) és térjünk vissza a kezdéshez. Ez úgy tűnik, könnyű egy kis városok száma, de ha kaptak száz őket, akkor nehéz lesz., A gráfelméletben, a számelméletben, a geometriában és a matematika és a számítástechnika más területein több ezer ilyen NP-teljes probléma ismert.
mi a válasz, tényleg?
ha fogadnék, akkor feltételezem, hogy a P nem egyenlő az NP-vel, és azt hiszem, a legtöbb szakértő egyetért. Szörnyen hülyének kellene lennünk, hogy ne lássuk, hogy a több ezer NP-teljes problémának nincs polinom idő algoritmusa. De fajként a hülye az alapértelmezett pozíciónk, így senki sem tudja megmondani, mi a válasz 100% – os bizonyossággal.,
ami érdekes a P vs NP probléma, hogy rámutat arra, hogy mennyire korlátozott a megértésünk annak bizonyításában, hogy bizonyos problémák nem rendelkeznek gyors megoldásokkal. Ez egy nagyobb téma része a számítási komplexitáselmélet területén, amely több tucat más komplexitási osztályt tanulmányoz. Nézze meg a komplexitás állatkert egy lista ezeket az osztályokat. A legtöbb esetben nyitva áll a különböző (gyakran egzotikus hangzású) komplexitási osztályok bemutatása, amelyek egymás megfelelő alosztályai. Például nem ismert, hogy az NL a P megfelelő alosztálya-e, és nem tudjuk, hogy az FPT a W megfelelő alosztálya-e.,
valódiságától függetlenül a P vs NP probléma valószínűleg egy ideig nyitva marad. Hacsak nem bizonyított, hogy P = NP, a Sudoku biztonságos marad.
Anthony Bonato