Matematika O čom je P ≠ NP
Alexander Razborov vsadil dvadsať centov. Matematik z Chicagskej univerzity prehrá s kolegom, keď sa ukáže, že dôkaz, ktorý pred dvoma týždňami zverejnil bonnský profesor počítačových vied Norbert Blum, je správny. Na druhej strane by bol Blum o milión dolárov bohatší. Pretože sa jeho dôkaz týka takzvaného problému P = NP, jedna zo šiestich matematických hádaniek, na riešenie ktorých vyčlenila americká Clay Foundation v roku 2000 milión. Siedma bola vyriešená už v roku 2002
Mediálne efektívne vysoké dotácie znamenajú osobitný vedecký význam týchto takzvaných problémov tisícročia, ale aj ich predpokladanú náročnosť, meranú aj z hľadiska životnosti matematika, ktorá bola premrhaná pri hľadaní riešení. Ale P = NP má medzi problémami milénia osobitné postavenie.
NP znamená: ťažko riešiteľné, ľahko kontrolovateľné
Nie je to v žiadnom prípade iba vedecky dôležité, pretože ovplyvňuje základnú technológiu dnešnej civilizácie, počítač. P a NP sú obe sady možných úloh, ktoré môžu byť spracované digitálnymi počítačmi pomocou algoritmov. Napríklad úloha triediť zoznam n čísel podľa veľkosti. Otázkou teraz je, ako rýchlo sa zvyšuje výpočtový čas s veľkosťou vstupu. Pri triedení potrebuje počítač, v horšom prípade, štvornásobne dlhší zoznam, ktorý je dvakrát tak dlhý - výpočtový čas sa zvyšuje kvadraticky alebo s n⊃2; Tento n⊃2; je jednoduchým príkladom toho, čo matematici nazývajú polynóm. Triedenie preto patrí do takzvanej triedy zložitosti P ako polynóm. To by zahŕňalo aj úlohu, pre ktorú je potrebný výpočtový čas, povedzme, s n⊃3; zvyšuje alebo n or1; ⁰ alebo n⊃3; + n⊃2;. Všetko sú to polynómy a moderné počítače všeobecne zvládajú problémy s P celkom dobre, aj keď majú vysoké n.
Pre mnoho úloh však nie sú známe žiadne algoritmy, ktoré by dokazovali, že patria do P, ale iba tie, ktorých výpočtový čas sa zvyšuje so vstupom, napríklad ako 2ⁿ, teda exponenciálne. Pri stále väčších vstupných dĺžkach n počítače spomalia tak rýchlo, že aj tie najvýkonnejšie sálové počítače budú po miliardy rokov obsadené prakticky relevantným n. Jedným z problémov, pre ktoré existujú iba také algoritmy, je rozklad n-ciferných čísel na faktory. Využívajú sa na to napríklad bežné metódy šifrovania na internete: Nemôžu byť priamo prelomené, ak je dĺžka kľúča n dostatočne veľká, pretože by to vyžadovalo takúto faktorizáciu a neexistuje metóda, pomocou ktorej by lámač kódov mohol v únosnom čase dosiahnuť svoj cieľ. . Čo tu však zostáva jednoduché - teda spracovať pomocou P-postupu - to je testovanie riešenia: Ak počítaču predstavíte predpokladaný prvočíselný faktor vstupného čísla, je pre neho ľahké rozpoznať, či je to v skutočnosti prvočíselný činiteľ vstupu . Postačuje jednoduché rozdelenie.
Takéto problémy, ktorých riešenia je možné rýchlo polynomicky skontrolovať, tvoria triedu NP. Z historických dôvodov skratka znamená „nedeterministický polynóm“ a nie „non-P“. Pretože ak sú výstupy P-algoritmov generované polynomiálne rýchlo, môžu byť samozrejme tiež polynomiálne rýchlo skontrolované. Takže P je podmnožinou NP.
Keby P = NP, svet by bol úplne iný.
Otázka však znie: Nemôže sa stať, že rýchla testovateľnosť riešenia vždy znamená rýchlu riešiteľnosť problému, aj keď zodpovedajúca metóda riešenia, algoritmus, ešte nebol nájdený? Potom by NP bol tiež v P, takže dve triedy by boli identické: P = NP. Nikto nevie, či je to tak. Ale nikto nevie, že to tak nie je.
Dnešné poznatky naznačujú, že P ≠ NP a celá svetová ekonomika je na nich založená, pokiaľ by už bez zabezpečeného šifrovania nefungovala. Môže sa však stať, že P = NP. A potom by bol svet úplne iným miestom.
Na jednej strane by potom už komunikácia nebola bezpečná. Matematik John Nash na to upozornil Americkú národnú bezpečnostnú agentúru v rokoch 1955 - 16 rokov pred formálnym sprísnením problému P = NP (ktorý by sa samozrejme rovnako ľahko dal nazvať problémom P P NP). Na druhej strane by bolo možné efektívne algoritmy predpovedať zloženie proteínov, čo by prinieslo revolúciu v medicíne. Optimalizačné úlohy v priemysle a výskume, ale aj v armáde, predpovede počasia, umelá inteligencia: kdekoľvek sa jedná o problémy NP, bol by možný pokrok, ktorého dôsledky pre každodenný život si autori sci-fi nemusia ani len predstaviť. Dôkaz, že P = NP by spočiatku iba teoreticky otvoril dvere, ale znalosť základnej uskutočniteľnosti by s veľkou pravdepodobnosťou uvoľnila obrovské energie na nájdenie efektívnych algoritmov.
Matematika, ktorá končí sama so sebou
Dopady P = NP by boli ešte ďalekosiahlejšie: v roku 1956, rok po Nashovom liste NSA, napísal Kurt Gödel, pravdepodobne najdôležitejší logik od Aristotela, list svojmu kolegovi Johnovi von Neumannovi, v ktorom opísal takmer desivý dôsledok P. = NP pre samotnú matematiku uznávaný: „Znamenalo by to jasné. že intelektuálna práca matematika by mohla byť v prípade otázok áno-nie úplne nahradená strojmi. “Kto preukáže N = NP, mohol by teoreticky nájsť aj algoritmus, ktorý nájde formálne dôkazy ďalších matematických viet - vrátane tých, ktoré sú predmetom šiestich Miléniové problémy stále pretrvávajú. Namiesto jedného potom zarobil šesť miliónov dolárov.
Dôkaz Norberta Bluma z 11. augusta teraz prichádza na jednej strane k upokojujúcemu a na druhej strane k nudnému záveru, že P ≠ NP. Iba: má pravdu?
Krátka odpoveď je, že 38 stránok práce musia najskôr skontrolovať odborníci, čo môže chvíľu trvať. Je pravda, že Alexander Razborov a ďalší vedci pôsobiaci v tejto oblasti sa stretli na seminári v Mathematical Research Center v Oberwolfach v Čiernom lese, len v týždni, keď Blum zverejnil svoju prácu na internete. Razborov si však neuvedomuje, že ktokoľvek z účastníkov sa dôkazy bližšie zaoberal. „Musíte vedieť, že sme mali prísny program,“ hovorí. Zostávalo to pri uzatváraní stávok.
Ten problém s klikami
Blum k problému pristupuje zo známej stránky: prostredníctvom takzvaného problému s klikou. Predstavte si školu s veľkým počtom študentov, každý sa pozná, ale nie každý sa pozná. Teraz dáte zoznam spárovaných známych počítaču s úlohou zistiť, či existuje skupina n študentov, ktorí sa všetci poznajú. Tento problém je NP a dokonca patrí do triedy problémov nazývaných NP-Complete. Jedná sa o NP a zároveň „NP-ťažké“, čo znamená, že každý ďalší problém v NP možno vysledovať späť k takémuto problému pomocou polynomiálneho úsilia. Dôkaz, že aj NP-úplný problém je v skutočnosti v P, by potom okamžite dokázal P = NP - a dôkaz, že nemôže byť v P, dokázať P ≠ NP.
Zobraziť celý obsah v pôvodnom príspevku
Algoritmy možno teraz mapovať na siete formálnych obvodov z logických spojení „a“, „alebo“ a z negácie a ukazujú, že počet potrebných spojení rastie iba polynomiálne so vstupom, aj keď to robí aj pôvodný algoritmus. Alexander Razborov v roku 1985, v tom čase ako doktorand v Moskve, dokázal, že kliková úloha sa nedá zvládnuť pomocou polynomiálneho vstupu z rastúcich sietí, ak obsahujú iba odkazy „a“ a „alebo“. Spoločnosť Blum teraz tvrdí, že prispôsobila dôkaznú metódu tak, aby Razborovova veta platila pre všetky siete vrátane sietí s negáciami. Čo znamená: Clique nikdy nie je v P - a kvôli NP-úplnosti problému s klikami, P ≠ NP.
Aj keď tomu dnes väčšina teoretických počítačových vedcov verí, v súčasnosti prevláda skepsa. Skutočnosť, že „nie“ - pridanie negácií v prepínacích sieťach - by malo mať túto moc, je možno tiež spochybnená, pretože táto možnosť musela byť pred odborníkmi už dlho. Pre matematika, ktorý sa k tejto téme vyjadril na internete, je Blumov dôkaz v istom zmysle príliš konvenčný, neukazuje prelomenie úplne nových ciest, ktoré by človek čakal od dôkazu vety, ktorú už toľko odborníkov našlo chybu. . Nemohol Alexander Razborov riskovať vyšší podiel v Oberwolfachu? „Stávka bola 1: 1 000,“ hovorí. "A môj kolega mi dal tých 20 centov okamžite." To možno interpretovať ako údaj o tom, ako hodnotí šancu. ““