Matematika Mi a P ≠ NP lényege
Alekszandr Razborov húsz centet fogadott. A Chicagói Egyetem matematikusa elveszíti egy kollégájától, amikor kiderül, hogy a bonn számítástechnika professzora, Norbert Blum által két hete közzétett bizonyítás helyes. Blum viszont egymillió dollárral lenne gazdagabb. Mivel bizonyítása az úgynevezett P = NP problémára vonatkozik, amely hat matematikai rejtvény egyike, amelyek megoldására az American Clay Foundation 2000-ben egymilliót különített el. A hetediket már 2002-ben megoldották
A médiában hatékony magas adottság jelzi ezeknek az úgynevezett millenniumi problémáknak a különös tudományos jelentőségét, de feltételezett nehézségüket is, a matematikus életének szempontjából is mérve, amelyet már elpazaroltak a megoldás keresésére. De P = NP különleges helyet foglal el a millenniumi problémák között.
Az NP jelentése: nehezen megoldható, könnyen ellenőrizhető
Ez korántsem csak tudományosan fontos, mivel kihat a mai civilizáció alapvető technológiájára, a számítógépre. A P és az NP mind a lehetséges feladatok halmaza, amelyeket digitális számítógépek algoritmusok segítségével feldolgozhatnak. Például az n számból álló lista méret szerinti rendezése. A kérdés most az, hogy a számítási idő milyen gyorsan növekszik a bemenet méretével együtt. Rendezéskor a számítógépnek a legrosszabb esetben négyszer olyan hosszúra van szüksége egy kétszer hosszabb listához - a számítási idő kvadratikusan vagy n or2-vel növekszik; Ez n⊃2; egy egyszerű példa arra, amit a matematikusok polinomnak neveznek. A rendezés tehát az úgynevezett P komplex osztályba tartozik, mint a polinom. Ez magában foglalna egy olyan feladatot is, amelyhez a szükséges számítási idő, mondjuk n3-mal; növekszik, vagy n⊃1; ⁰ vagy n⊃3; + n⊃2; Ezek mind polinomok, és a modern számítógépek általában nagyon jól kezelik a P problémákat, még magas n esetén is.
Számos feladat esetében azonban nem ismertek algoritmusok, amelyek igazolják, hogy P-hez tartoznak, csak azok, amelyek számítási ideje a bemenettel együtt nő, például 2 like, azaz exponenciálisan. Az egyre nagyobb n bemeneti hosszúság esetén a számítógépek olyan gyorsan lelassulnak, hogy még a legerősebb nagyszámítógépeket is gyakorlatilag releváns n foglalja el évmilliárdokra. Az egyik probléma, amelyre csak ilyen algoritmusok léteznek, az n jegyű számok tényezőkre bontása. Ezt például az interneten szokásos titkosítási módszerekkel használják: Nem lehet őket közvetlenül feltörni, ha az n kulcshossz elég nagy, mert ehhez ilyen tényezőre lenne szükség, és nincs olyan módszer, amellyel egy kódmegszakító tűrhető időn belül elérhetné célját. . Ami azonban itt továbbra is egyszerű - vagyis P-eljárással feldolgozható - az a megoldás vizsgálata: Ha a bemeneti szám feltételezett prímtényezőjét bemutatja a számítógépnek, akkor könnyen felismeri, hogy valóban a bemenet prímtényezője . Elegendő egy egyszerű felosztás.
Az ilyen problémák, amelyek megoldásai polinomiálisan gyorsan ellenőrizhetők, alkotják az NP osztályt. Történelmi okokból a rövidítés a "nem-determinisztikus polinom" kifejezés, és nem a "nem-P". Mivel ha a P-algoritmusok kimeneteit polinomiálisan gyorsan generálják, akkor természetesen polinomiálisan is gyorsan ellenőrizhetők. Tehát P az NP részhalmaza.
Ha P = NP, akkor a világ teljesen más lenne.
De a kérdés a következő: Nem lehet, hogy a megoldás gyors tesztelhetősége mindig a probléma gyors megoldhatóságát jelenti, még akkor is, ha a megfelelő megoldási módszert, az algoritmust még nem találták meg? Ekkor az NP is P-ben lenne, tehát a két osztály azonos lenne: P = NP. Senki sem tudja, hogy ez a helyzet. De senki sem tudja, hogy ez nem így van.
A mai ismeretek azt sugallják, hogy a P ≠ NP és az egész világgazdaság ezen alapul, amennyiben biztonságos titkosítás nélkül már nem működne. De lehet, hogy P = NP. És akkor a világ egy teljesen más hely lenne.
Egyrészt a kommunikáció akkor már nem lenne biztonságos. John Nash matematikus 1955-ben - 16 évvel azelőtt, hogy a P = NP problémát (amelyet ugyanolyan könnyen lehet P called NP problémának is nevezni) hivatalosan szigorúvá tették - felhívta az Amerikai Nemzetbiztonsági Ügynökséget. Másrészt hatékony algoritmusokkal lehetne megjósolni például a fehérjék hajtogatását, ami forradalmasítani fogja az orvostudományt. Optimalizálási feladatok az iparban és a kutatásban, de a katonaságban is, időjárás-előrejelzések, mesterséges intelligencia: bárhol is vannak NP-problémák, előrelépés lehetséges, amelynek következményeit a mindennapi életre a fantasztikus szerzők sem tudják elképzelni. Bizonyíték arra, hogy P = NP kezdetben csak elméletileg nyitja meg az ajtót, de az alapvető megvalósíthatóság ismerete nagy valószínűséggel hatalmas energiákat szabadít fel a hatékony algoritmusok megtalálásához.
A matematika, amely önmagát megszünteti
A P = NP következményei még nagyobb horderejűek lennének: 1956-ban, egy évvel Nash NSA-hoz intézett levele után Kurt Gödel, valószínűleg Arisztotelész óta a legfontosabb logikus, levelet írt kollégájának, John von Neumann-nak, amelyben leírta P. szinte óriási következményeit. = A matematika NP maga is felismerte: „Világot jelentene. hogy a matematikus szellemi munkáját igen-nem kérdések esetén teljesen helyettesíthetik gépekkel. ”Aki bebizonyítja, hogy N = NP, elméletileg találhat olyan algoritmust is, amely más matematikai tételek formális bizonyítékát is megtalálja - beleértve azokat is, amelyek a hat tárgyát képezik. A millenniumi problémák még mindig megoldatlanok. Egy helyett aztán hatmillió dollárt keresett.
Norbert Blum augusztus 11-i bizonyítéka most egyrészt megnyugtató, másrészt unalmas következtetésre jut, hogy P ≠ NP. Csak: igaza van?
A rövid válasz az, hogy a 38 oldalas munkát először szakértőknek kell ellenőrizniük, ami időbe telhet. Igaz, hogy Alexander Razborov és más, ezen a területen dolgozó kutatók egy workshopon találkoztak a Fekete-erdőben, Oberwolfachban, a Matematikai Kutatóközpontban, éppen azon a héten, amikor Blum munkáját az internetre tette. Razborovnak azonban nincs tudomása arról, hogy a résztvevők között bárki jobban megvizsgálta volna a bizonyítékokat. "Tudnod kell, hogy szoros volt az időbeosztásunk" - mondja. Maradt a fogadás.
Ez a probléma a klikkekkel
Blum ismerős oldalról közelíti meg a problémát: az úgynevezett klikkproblémán keresztül. Képzeljünk el egy olyan iskolát, ahol nagy a létszám, mindenki ismeri egymást, de nem mindenki ismeri egymást. Most átadja a párosított ismerősök listáját egy számítógépnek azzal a feladattal, hogy kiderítse, létezik-e n tanulócsoport, akik mind ismerik egymást. Ez a probléma NP, és még az NP-complete nevű probléma osztályába is tartozik. Ezek NP és egyúttal "NP-nehezek", ami azt jelenti, hogy az NP bármely más problémája polinomiális erőfeszítéssel visszavezethető ilyen problémára. Az a bizonyíték, hogy még egy NP-teljes probléma is P-ben van, azonnal bebizonyítja, hogy P = NP -.
A teljes tartalom megjelenítése az eredeti bejegyzésben
Az algoritmusok már leképezhetők a formális áramkörhálózatokra az „és”, „vagy” logikai kapcsolatokból és a negációból, és megmutatják, hogy a szükséges kapcsolatok száma csak polinomikusan növekszik a bemenettel, még akkor is, ha az eredeti algoritmus ezt is megteszi. Alekszandr Razborov 1985-ben, akkoriban Moszkvában doktoranduszként bebizonyította, hogy a klikkfeladatot nem lehet elsajátítani a növekvő hálózatok polinomiális bemenetével, feltéve, hogy ezek csak „és” és „vagy” linkeket tartalmaznak. Blum most azt állítja, hogy a bizonyítási módszert úgy adaptálta, hogy Razborov tétele minden hálózatra vonatkozik, beleértve a tagadásokat is. Ami azt jelenti: a Clique soha nincs P-ben - és a klikkprobléma NP-teljessége miatt P ≠ NP.
Bár manapság ez az elméleti informatikusok véleménye, a szkepticizmus jelenleg érvényesül. Az is kétséges, hogy a „nem” -nek - a negatívak hozzáadásához a hálózatváltáshoz - ez a hatalom kell, hogy legyen, mert ennek a lehetőségnek már régóta a szakértők előtt kellett lennie. Egy olyan matematikus számára, aki a témát az interneten kommentálta, Blum bizonyítása bizonyos értelemben túl konvencionális, nem mutatja meg olyan teljesen új utak törését, amelyeket elvárhatna egy olyan tétel bizonyításától, amelyben már annyi szakértő talált hibát . Nem kockáztathatta volna Alekszandr Razborov nagyobb részesedést Oberwolfachban? "A fogadás 1: 1000 volt" - mondja. - És kollégám azonnal megadta a 20 centet. Ezt úgy lehet értelmezni, hogy jelzi, hogyan értékeli az esélyt. "