Ez a cikk eredetileg megjelent alaplap Németország. Mivel az eredeti kiadvány már frissült az új információkat alaplap minket. Mi a közös a gyógyítható rákban, a tisztességes kapitalizmusban és a Super Mario Bros tökéletes játékában? Egy matematikai elmélet szerint ezeknek a problémáknak a megoldása lehetővé tenné számunkra, hogy gyorsan megoldjuk a többieket., Minden, ami szükséges jobb algoritmusok bizonyítani, hogy a bonyolult kérdések—mint például a fehérje, összecsukható, hatékony piacok, valamint a kombinatorikus elemzések—csupán variációk egyszerűbb problémák, kimondottan már képes megoldani. De hogyan lehet egy algoritmus egyszerűsíteni a rendkívül bonyolult problémákat? Ez egy másik kérdéstől függ: mi van, ha a bonyolult problémák valójában csak egyszerű problémák álruhában?, Ez a rejtély továbbra is a modern matematika egyik legnagyobb megoldatlan kérdése, egyike a hét Millenniumi díj problémájának, amelyért minden elfogadott választ egymillió dollárral jutalmaznak.
egy Norbert Blum nevű német férfi azt állította, hogy megoldotta a fenti rejtvényt, amelyet megfelelően P vs NP problémának neveznek. Sajnos az állítólagos megoldása nem hordoz jó hírt., Blum, aki a Bonni Egyetemen van, a közelmúltban közzétett 38 oldalas cikkében azt állítja, hogy a P nem egyenlő az NP-vel. Más szavakkal, a bonyolult problémák alapvetően különböznek az egyszerű problémáktól, és nem úgy tűnik, hogy a nagy teljesítményű számítógépeink bármikor képesek lesznek ezeket a legnehezebb problémákat a közeljövőben megoldani. Az újság megjelenése óta eltelt napokban számos matematikus kezdett kérdéseket feltenni arról, hogy Blum egyáltalán megoldotta-e.
pontosan mi a P versus NP probléma?,
a legtöbb számítógépes tudós általában egyetért Blum következtetésével. A kemény problémák kemények, a könnyű problémák könnyűek. A számítástechnikában az egyszerű problémák általában a P. banner alá tartoznak. ez azt jelenti, hogy “polinom időben” megoldhatók, ami nagyon hasonlít arra, hogy ésszerű időn belül megoldhatók. Sokkal nehezebbek az NP problémák, amelyeket a számítógépek ésszerű időkeretben nem tudnak megoldani. Gyakorlati célokra az NP-problémák akár a számítógépek által is megoldhatatlanok lehetnek., (Megjegyezzük azonban, hogy az NP jelentése “nem determinisztikus polinom idő” helyett “nem polinom” idő.) Íme néhány példa az NP problémákra:
Protein összecsukható: az a folyamat, amelyen keresztül a biológiai szervezetben lévő fehérjék megkapják szerkezetüket. A folyamatba való jobb betekintés segíthet felismerni vagy akár megakadályozni a mutációkat, amelyek gyógyíthatják a rák bizonyos formáit. Optimalizált útvonalkeresés: optimalizált utazási útvonal 15 különböző városon keresztül anélkül, hogy kétszer meglátogatná ugyanazt a várost?, Kemény dió feltörni, még egy szuperszámítógép számára is, ezért ezt a számítástechnika NP problémájának is tekintik.
a tökéletes sakkjátéknak végtelen lehetséges mozdulatai vannak, így még egy hihetetlen képességű szuperszámítógép sem tudja meghatározni a tökéletes taktikát. Sok matematikus úgy véli, hogy ez a probléma olyan nehéz, hogy nem tartják NP probléma, hanem úgy, hogy teljesen ki a birodalmából lehetőséget.,
ezeknek az összetett problémáknak egy közös vonása van: bármennyire nehéz megoldást találni az NP problémákra, viszonylag könnyű ellenőrizni a megoldások érvényességét, ha megvan.
Ez a két kategorikus különbség a probléma összetettségében az otthoni számítógépek társadalmi felemelkedése előtt származik. Az 1970-es években, amikor a számítógépek még mindig egy nehézkes hűtőszekrény méretűek voltak, gyorsan meghatározták, hogy az emberiség összes problémáját nem lehet egyszerűen megoldani ezek a gépek., Azt javasolták, hogy a különbségtétel formalizálható legyen a számítási komplexitás szempontjából, ami komplexitási osztályokhoz vezet, beleértve az N-t és az NP-t is.
A P és az NP 1971-es formális meghatározása óta a számítógépes tudósok vitatják, hogy lehetséges-e olyan algoritmust kidolgozni, amely képes az NP-problémák csökkentésére vagy újradefiniálására, hogy polinom időben megoldhatók legyenek. Ha valaki bizonyítani tudja, hogy az összes NP-probléma végül csak a P-problémák változatai, akkor az összes NP-probléma lényegében azonos csökkentési formának lenne kitéve., Más szóval, aki ismeri a tökéletes Super Mario Bros taktikát, gyógyíthatja a rákot is.
összesen 116 legbátrabb a saját területén hivatalosan is megpróbálta megoldani ezt a rejtélyt (bár elmondhatatlan több számítógépes tudós írt volna megoldást messageboards és oldalak, mint például arXiv). A mai napig ezen bizonyítékok egyikét sem ismerte el hivatalosan a matematikai közösség.
egyfajta, aki milliomos akar lenni?, a matematikusok számára
2000 – ben az Oxfordban található Clay Mathematics Institute (CMI) összeállította a hét megoldatlan Millenniumi Díjprobléma listáját, minden megoldásért egymillió dollárt ígérve. Ez egyfajta, aki azt akarja, hogy egy milliomos? vagy X díjat matematikusok. A Millenniumi díj problémáit még szakértői körökben is rendkívül nehéznek tartják. A kérdések megértéséhez rengeteg területspecifikus tudás szükséges., Az egyetlen Millenniumi díj probléma, amelyet eddig megoldottak, a Poincaré-sejtés,amelyet nem könnyű megmagyarázni egy másik matematikai koncepcióról szóló cikkben.
az NP probléma megoldása nem lenne teljesen jó dolog. Például a legtöbb titkosítás a nagyon nagy prímszámok faktorálásának nehézségén alapul. Az egész faktorizáció egy NP osztályú probléma. A 256 bites kódot, például azokat, amelyeket a pénzügyi intézmények használnak az online hitelkártyás fizetésekben, törhetetlennek tekintik, így nagyon biztonságosnak., Ha valaki bebizonyítaná, hogy az NP egyenlő P-vel, a bankoknak gyorsan más biztonsági módszerrel kell előállniuk.
mit gondolnak a matematikusok Blum matematikai bizonyítékáról?
A Blum dolgozatának megjelenése óta a matematikusok és a számítástechnikusok világszerte azon törik a fejüket, hogy a bonni székhelyű kutató valóban megoldotta-e ezt a Millenniumi díjat. Egy kezdetben pozitív reakció után, mint például Reza Zadeh Stanford matematikus, kétségek merülnek fel azzal kapcsolatban, hogy Blum érvelése helyes-e.,
az elméleti matematika fórumán Mikhail nevű felhasználó felkereste Alexander Razborovot—a papír szerzőjét, amelyen Blum bizonyítéka alapul -, hogy megkérdezze őt Blum papírjáról. Razborov azt állítja, hogy hibát fedezett fel Blum cikkében: Blum fő érvelése ellentmond Razborov egyik legfontosabb feltételezésének. És matematikus Scott Aaronson, aki valami hatóság a matematikai közösség, amikor a P vs., NP, azt mondta, hogy hajlandó fogadni $200,000 hogy Blum matematikai bizonyítéka nem fog elviselni. “Kérem, ne kérdezzen” – írja Aaronson. Ha a bizonyítékot nem cáfolták meg, ” visszajöhetsz, és elmondhatod, hogy zártkörű bolond voltam.”Az Aaronson kezdeti blogbejegyzése óta eltelt héten más matematikusok elkezdték lyukasztani Blum bizonyítékát. Dick Lipton, a Georgia Tech számítástechnikai professzora egy blogbejegyzésben azt írta, hogy Blum bizonyítéka “sok komoly szűrőt átad”, de azt javasolta, hogy legyen némi probléma vele., A kommentátor, hogy a blogbejegyzést, ismert csak ” vloodin, “megjegyezte, hogy volt egy” egyetlen hiba egy finom pont ” a bizonyíték; más matematikusok azóta csimpaszkodott, és megerősítette vloodin kezdeti elemzés, és így a feltörekvő konszenzus sok matematikus, hogy a megoldás p vs.NP továbbra is megfoghatatlan. Fordította: Melina McCormack.