Tento článek se původně objevil na základní desce Německo. Od své původní publikace byla aktualizována novými informacemi od společnosti Motherboard US. Co mají společného léčitelná rakovina, spravedlivý kapitalismus a dokonalá hra Super Mario Bros.? Podle matematické teorie by řešení kteréhokoli z těchto problémů umožnilo rychle vyřešit ostatní., Vše, co je potřeba, jsou lepší algoritmy dokázat, že na složité otázky—jako je skládání bílkovin, efektivní trhy, a kombinatorické analýzy—jsou pouze variace na jednodušší problémy, které superpočítače jsou již schopni řešit. Ale jak může jeden algoritmus zjednodušit extrémně složité problémy? To záleží na další otázce: co když komplikované problémy jsou opravdu jen jednoduché problémy v přestrojení?, Tato hádanka zůstává jednou z největších nevyřešených otázek moderní matematiky a je jedním ze sedmi problémů milénia Prize, za které je každá přijatá odpověď odměněna jedním milionem dolarů.
Nyní, německý muž jménem Norbert Blum má tvrdil, že vyřešil výše hádanku, která je vhodně známý jako P vs. NP problém. Jeho domnělé řešení bohužel nepřináší dobré zprávy., Blum, který pochází z University of Bonn, ve svém nedávno publikovaném 38stránkovém dokumentu tvrdí, že P se nerovná NP. Jinými slovy, složité problémy jsou zásadně jiné než jednoduché problémy a nevypadá to, že náš vysoký výkon počítače bude schopen rozlousknout ty nejtěžší problémy kdykoliv v blízké budoucnosti. A ve dnech, kdy jeho práce byla zveřejněna, četné matematici začali klást otázky o tom, zda Blum vyřešit vůbec.
co přesně je P versus NP problém?,
většina počítačových vědců má tendenci souhlasit s blumovým závěrem. Těžké problémy jsou těžké, snadné problémy jsou snadné. V oblasti počítačové vědy, jednoduché problémy obvykle spadají pod praporem P. To znamená, že mohou být řešeny v „rozumném čase“, což je hodně, jako říkat, že mohou být řešeny v přiměřené lhůtě. Mnohem obtížnější jsou problémy NP, které počítače nejsou schopny vyřešit v rozumném časovém rámci. Pro praktické účely mohou být problémy s NP také neřešitelné počítači., (Všimněte si však, že NP znamená“ nedeterministický polynomický čas „spíše než“ ne polynomický “ čas.) Zde jsou některé příklady problémů NP:
skládání bílkovin: proces, kterým proteiny v biologickém organismu získávají svou strukturu. Lepší vhled do tohoto procesu by nám mohl pomoci rozpoznat nebo dokonce bránit mutacím, které by mohly vyléčit určité formy rakoviny. Optimalizovaný routefinding: optimalizovaná cestovní trasa přes 15 různých měst, aniž byste dvakrát navštívili stejné město?, Tvrdý oříšek k prasknutí, a to i pro superpočítač, což je důvod, proč je to také považováno za problém NP v informatice.
perfektní šachy: šachy, má nekonečné možných tahů, tak, že i superpočítač s neuvěřitelnou kapacitu nelze určit ideální taktika. Mnoho matematiků považuje tento problém za tak obtížný, že jej nepovažují za problém NP, ale spíše jej považují za zcela mimo oblast možností.,
všechny tyto složité problémy mají jednu společnou věc: jak obtížné může být najít řešení problémů s NP, je relativně snadné zkontrolovat platnost řešení, jakmile je máte.
tyto dvě kategorické rozdíly ve složitosti problémů mají původ před společenským vzestupem domácích počítačů. V 70. letech, kdy počítače stále měly velikost neohrabané ledničky, bylo rychle zjištěno, že ne všechny problémy lidstva by tyto stroje mohly jednoduše vyřešit., Bylo navrženo, že rozdíl by mohl být formalizován z hlediska výpočetní složitosti, což vede k sadě tříd složitosti, včetně n a NP.
Od formální definice P a NP v roce 1971, počítačové vědci diskutovali, zda by bylo možné přijít s algoritmem, který je schopen snížit nebo předefinování NP problémy, které mohou být řešeny v polynomiálním čase. Pokud by někdo dokázal, že všechny problémy s NP jsou nakonec jen variace problémů s P, pak by všechny problémy s NP v podstatě podléhaly stejné formě redukce., Jinými slovy, kdokoli zná dokonalou taktiku Super Mario Bros., mohl by také vyléčit rakovinu.
celkem 116 nejodvážnější ve svém oboru se oficiálně pokusil vyřešit tuto záhadu (i když nevýslovné více počítači vědci posted by-být řešení messageboards a na místech, jako je arXiv). K dnešnímu dni žádný z těchto důkazů nebyl oficiálně uznán matematickou komunitou.
jakýsi, kdo chce být milionářem?, pro Matematiky
V roce 2000 Clay Mathematics Institute (CMI), který se nachází v Oxfordu, sestavil seznam sedmi nevyřešených Millennium Prize Problems, jištění jednoho milionu dolarů pro každého řešení. Je to jakýsi, kdo chce být milionářem? nebo X cena pro matematiky. Problémy s cenou Millennium jsou považovány za mimořádně obtížné i v odborných kruzích. K pochopení otázek je třeba i množství znalostí specifických pro danou oblast., Jediným dosud řešeným problémem milénia je Poincaré domněnka, kterou nelze snadno vysvětlit jako vedlejší článek o jiném matematickém pojetí.
řešení problému NP by nebylo úplně dobré. Například většina šifrování je založena na obtížnosti factoringu velmi velkých prvočísel. Celočíselná faktorizace je problém třídy NP. 256bitový kód, jako jsou ty, které finanční instituce používají při platbách online kreditní kartou, je považován za nerozbitný, a tedy velmi bezpečný., Pokud by někdo dokázal, že NP dělá stejné P, banky by musely rychle přijít s jinou bezpečnostní metodou.
co si matematici myslí o blumově matematickém důkazu?
Od Blum dokument byl zveřejněn, matematiků a počítačových vědců po celém světě byly láme hlavu, zda Bonn-based pracovník má, ve skutečnosti, to vyřešil Millennium Prize Problém. Po původně pozitivní reakce, jako je ten ze Stanfordu matematik Reza Zadeh, pochybnosti začínají objevovat informace o tom, zda Blum úvaha je správná.,
V fórum pro teoretické matematiky, uživatel jménem Michail natáhl Alexander Razborov—autor papíru, na který Blum důkaz je založen—požádat ho o Blum papíru. Razborov údajně objevil chybu v Blumově dokumentu: Blumův hlavní argument je v rozporu s jedním z Razborovových klíčových předpokladů. A matematik Scott Aaronson, který je něco jako autorita v matematické komunitě, pokud jde o p vs., NP, řekl, že by byl ochoten vsadit $200,000, že blumův matematický důkaz nevydrží. „Prosím, přestaň se ptát,“ píše Aaronson. Pokud důkaz nebyl vyvrácen, “ můžete se vrátit a říct mi, že jsem byl uzavřený blázen.“V týdnu od Aaronson původní blog post, další matematici začali se snaží prorazit díry v Blum je důkaz. Dick Lipton, profesor informatiky na Georgia Tech, napsal v blogu, že blumův důkaz „prochází mnoha filtry závažnosti“, ale navrhl, že s tím mohou být nějaké problémy., Komentátor na tomto blogu, známý jen jako „vloodin,“ poznamenal, že tam bylo „jediné chyby na jemné bodu“ v důkazu; další matematici od té doby se ozval a potvrdil vloodin počáteční analýzy, a tak rodící se konsensus mezi mnoha matematiků je, že řešení problému P vs. NP zůstává nepolapitelný. Přeložila Melina Mccormacková.