Pro vítěze Turingovy ceny je vše jen výpočet a některé problémy jsou neřešitelné

Průkopnická práce Aviho Wigdersona o náhodnosti prosadila myšlenku, že některé problémy mohou jednoduše přesahovat i ty nejvýkonnější počítače.

„Je to jedna z nejzákladnějších intelektuálních otázek, jaké byly kdy položeny,“ říká Avi Wigderson, držitel ceny ACM Turing Award 2024, k otázce P=NP. "Pokud se všichni mýlí a P se rovná NP, má to úžasné důsledky."

Asociace pro výpočetní techniku (ACM) ve středu oznámila, že udělila letošní cenu A.M. Turingovu cenu, často označovanou jako Nobelova cena za výpočetní techniku, získal počítačový vědec a matematik Avi Wigderson z Institutu pro pokročilá studia v Princetonu v New Jersey.

Wigderson byl oceněn za zásadní příspěvky, které posunuly to, co je známo jako teorie počítání, se zvláštním rozdílem v „přetvoření našeho chápání role náhodnosti ve výpočtech“ a „desetiletí intelektuálního vedení v teoretické informatice,“ uvedl ACM.

Cena pojmenovaná po britském matematikovi a počítačovém vědci Alana M. Turingovi je spojena s cenou 1 milion dolarů s finanční podporou poskytnutou společností Google.

Wigderson, profesor Herberta H. Maass v institutu, prokázal po desetiletí hluboké chápání počítání jako více než jen stroje. Počítání je fenomén vyskytující se v celém vesmíru.

"Výpočet je opravdu zásadní pojem," řekl Wigderson v rozhovoru pro ZDNET. "Nejde jen o algoritmy v počítačích: vše se počítá."

"Když na pláži uvidíte mušli s nějakým pozoruhodným vzorem, který byl vypočítán velmi jednoduchými kroky: Vyrostla z jednoho zrna a lokálně tato zrna vypočítala sousední zrna a byla spojena - tento opravdu jednoduchý proces rozvíjejte to a získáte úžasné vzory."

Tato jednoduchá pravidla lokální, postupné změny - „která velmi dobře známe,“ řekl Wigderson - „mohou vytvářet velmi složité jevy.“ Výpočtových příkladů je mnoho. Výpočet je způsob, jak se oplodněné vajíčko stane lidskou bytostí nebo jak se lidské buňky během života dělí. "Také drby," dodal Wigderson. "Když řeknete něco, co vám bylo řečeno, nebo na Facebooku - způsob, jakým se informace vyvíjejí, jsou to výpočetní otázky, které lze zarámovat do kompletních výpočetních modelů."

Udělení Turingovy ceny Wigdersonovi je obzvláště vhodné, protože jeho obor, Teorie počítání, začal Turing v roce 1936 Turingovým přelomovým dokumentem „O vyčíslitelných číslech, s aplikací na problém Entscheidungs“.

Turing položil základy pro extrémně širokou definici počítání jako evoluce prostředí prostřednictvím místních, postupných změn, kde „prostředím“ mohou být lidské bytosti, galaxie, mušle na pláži, informace nebo libovolný počet jevů.

Nahlíženo optikou Turinga, jak po desetiletí vyvíjel Wigderson a kolegové, každý přírodní jev je výpočet. "Jak termiti staví tyto hrady nebo včely, které nějak vědí, kam jít a hledat med - ve skutečnosti se vyvíjejí, aby tvořily, i když mají velmi malé mozkové buňky," vysvětlil Wigderson.

Cena oceňuje Wigderson konkrétně za jeho příspěvek k pochopení role, kterou hraje náhodnost ve výpočtech. Konvenční počítače, od sálových počítačů po iPhony, jsou „deterministické“; to znamená, že následují předvídatelný vzor kroků. Ale mnoho z nejzajímavějších příkladů počítání v přírodě zahrnuje prvky náhodnosti, od lastur až po shlukování špačků známé jako mumraj.

Wigderson a jeho spolupracovníci využili zkoumání náhodnosti, aby pokročili v pochopení toho, jaké problémy lze a nelze „efektivně“ vypočítat. Ve světě existuje mnoho problémů - ve vědě, matematice a inženýrství - pro které neexistují žádné známé účinné algoritmy, což znamená algoritmus, který může pracovat v "polynomiálním čase", spíše než v exponenciálním čase.

Například faktorizace velkých celých čísel na jejich prvočísla nemá známý algoritmus, který by mohl běžet v kratším než exponenciálním čase. Ale nestačí najít takový algoritmus; počítačoví vědci a matematici chtějí tak či onak dokázat, s jistotou vědět, zda mohlo existovat řešení pro takové "těžké" problémy.

Tři primární články citované ACM tvoří sekvenci, progresi, řekl Wigderson ZDNET.

"Otázkou bylo, jak mocná je náhodnost v algoritmech," řekl Wigderson. Počínaje osmdesátými lety našli počítačoví vědci mnoho způsobů, jak použít náhodnost jako cestu k účinným algoritmům. "A tak to vypadalo, že náhodnost je velmi mocná."

"Tato díla měla za cíl ukázat, že náhodnost není tak mocná," řekl. Místo toho Wigderson a kolegové vyvinuli generátory pseudonáhodných čísel, které by mohly vyřešit některé těžké problémy účinným, deterministickým způsobem.

"Ve všech těchto článcích si vezmete těžký problém a vytvoříte pseudonáhodný generátor, který dokáže deterministicky generovat bity, které vypadají náhodně, a můžete nahradit náhodné vstupy v pravděpodobnostním algoritmu [a vytvořit] deterministický."

Odplevelení náhodnosti, její nahrazení deterministickým přístupem, vyvrcholilo v závěrečné práci s nejsofistikovanějším generátorem pseudonáhod. Poučení, poznamenal Wigderson: "Mohli bychom dojít k závěru, že jakýkoli polynomiálně-časově pravděpodobný algoritmus může být vytvořen jako polynomiálně-časově deterministický."

Překvapivým vedlejším efektem těchto objevů je, že pokud dokážete z algoritmu odstranit náhodnost, můžete prokázat tvrdost problému - nápadný způsob, jak vyřešit otázku, zda problém je nebo není těžký. .

"Tyto dva pojmy [náhodnost a tvrdost], které jsou velmi odlišné, jsou nějak úzce propojeny, " řekl Wigderson. "Jsou téměř totéž. Odstranění náhodnosti z pravděpodobnostních algoritmů a prokázání náročnosti výpočetních problémů jsou tak trochu duální problémy."

Pro ty, kteří se chtějí ponořit hlouběji do práce o náhodnosti, jsou články uvedeny níže. Můžete si však přečíst kapitolu o náhodnosti ve velkém Wigdersonově svazku „Math and Computation“, který je k dispozici ke stažení zdarma. Když tu knihu prolistujete, budete na příštím koktejlovém večírku hlavou a rameny nad většinou lidí.

• "Tvrdost vs. náhodnost" (ve spolupráci s Noamem Nisanem)
  Tento článek mimo jiné představil nový typ pseudonáhodného generátoru a dokázal, že účinná deterministická simulace randomizovaných algoritmů je možná za mnohem slabších předpokladů, než bylo dříve známo.

• "BPP má subexponenciální simulace času, pokud EXPTIME nemá zveřejněné důkazy" (spoluautoři László Babai, Lance Fortnow a Noam Nisan)
  Tento článek použil `amplifikaci tvrdosti' k demonstraci toho, že pravděpodobnostní polynomický čas s omezenou chybou (BPP) může být simulován v subexponenciálním čase pro nekonečně mnoho vstupních délek za slabších předpokladů.

• "P=BPP, pokud E vyžaduje exponenciální obvody: Derandomizace lemmatu XOR" (spoluautor s Russellem Impagliazzo)
  Tento článek představuje silnější pseudonáhodný generátor s v podstatě optimálními kompromisy mezi tvrdostí a náhodností.

Pro Wigdersona (67) bylo potěšení z vytahování překvapivých souvislostí hnacím impulsem již od raného věku.

"Vždy jsem miloval matematiku od raného dětství," řekl Wigderson. "Můj táta mě zajímal o hádanky a tak."

Wigderson vystudoval izraelský Technion (Institute of Technology) a získal magisterské a doktorské tituly v počítačových vědách na Princetonské univerzitě. Dojemnou řeč o jeho zážitcích nabízí Wigdersonova děkovná řeč v loňském roce, kdy obdržel čestný doktorát od Technion.

„Opravdu mi záleží na formalizaci výpočtových modelů,“ řekl Wigderson k tomu, co ho zajímá, „například jestli je nějaký kryptografický protokol bezpečný nebo doba běhu nějakého algoritmu je taková a taková.

"Skutečnost, že se zabývá tímto základním pojmem, ale je to ve skutečnosti matematický obor, je pro mě velmi cenná."

Mezi úspěchy, na které je nejpyšnější, řekl Wigderson, patří jeho práce, která pokročila v to, čemu se říká „důkazy s nulovými znalostmi“, kde lze informace udržet v tajnosti, ale dvě protistrany se přesto mohou dohodnout. "Řekněme, že něco vím, vím, kdo vyhraje volby, a vy mi nevěříte, a já se vás snažím přesvědčit [o tom, že opravdu vím]. Existuje způsob, jak vás přesvědčit, aniž bych vám to řekl něco, co jsi ještě nevěděl."

Ve skutečnosti je takový stav věcí kořenem kryptografie s veřejným klíčem, kde každá strana skrývá svůj soukromý klíč, ale je schopna přesvědčit druhou, že autoritativně podepsala například elektronickou smlouvu. "Je to naprosto paradoxní představa," řekl Wigderson o takových důkazech s nulovými znalostmi. "Tohle je ten druh věcí, které vás napadají, když si myslíte, že něco takového může existovat."

Wigdersonův intelekt vyvažuje potěšení s bystrým smyslem pro základní význam. Pro společnost má velký význam například otázka, které problémy jsou prokazatelně těžké.

Jak bylo formulováno v 70. letech 20. století, fráze „Má P=NP?“ se ptá, zda by problém, jehož řešení lze ověřit, mohl být také nakonec vyřešen pomocí polynomiální časové rovnice - efektivně vyřešen. Pokud ano, pak by mohl být pravděpodobně sestaven počítač, který by v praktických časových rozpětích vyřešil některé zdánlivě neřešitelné problémy světa.

"Je to jedna z nejzákladnějších intelektuálních otázek, jaké byly kdy položeny," řekl Wigderson z P=NP. Jeho osobní domněnka, která se v jeho oboru shoduje, je, že P nenírovná se NP, což znamená, že některé problémy nelze efektivně vyřešit.

"Pokud se všichni mýlí a P se rovná NP, má to úžasné důsledky," řekl Wigderson. "Prakticky jakýkoli problém, který chcete vyřešit, můžete vyřešit efektivně - cokoliv; můžete vyléčit rakovinu."

"Pokud se P nerovná NP, důsledky pro věci mimo náš dosah jsou poměrně významné," řekl Wigderson. Jednak by to znamenalo, že některé prvky lidského myšlení, jako je kreativita, by mohly být mimo dosah počítačů, protože neexistuje způsob, jak efektivně simulovat heuristiku, lidský smysl pro věci, které se týkají například umělecké tvorby. .

Ale sklenice je z poloviny plná, v jiném smyslu: Pokud problémy NP nelze vyřešit efektivně, znamená to, že kryptografie - celý základ moderní ekonomiky - je bezpečná před prasknutím, poznamenal Wigderson.

Zda se P rovná nebo nerovná NP, je otevřená otázka. "Doufal jsem, že to za mého života uvidím někdo dokázat, teď o tom pochybuji," řekl Wigderson.

Kvantový počítač také není snadnou odpovědí na tuto bezvýchodnou situaci. "Přemýšlejte o kvantovém počítači: tohle neexistuje," řekl Wigderson. „Nevíme, jestli někdy bude existovat“ - i když o tom intenzivně teoretizují IBM, Google a další.

Pokud je P=NP otevřeným problémem, je to také otázka okamžiku: Co může umělá inteligence - včetně strojů „umělé obecné inteligence“ - udělat nebo neudělat, aby se vyrovnala lidskému myšlení? Představa, že vše ve vesmíru se počítá, jistě znamená, že umělá inteligence by měla být schopna dosáhnout určité míry lidských schopností.

"My jsme uhlík a oni jsou křemík, takže materiál je jiný, ale potíže jsou na psychologické úrovni, ne na provozní úrovni," je Wigdersonův pohled. Umělá inteligence již prokázala, že „dokáže vyřešit spoustu problémů, které jsme dříve nevěděli, jak vyřešit,“ řekl Wigderson. Zná "některé významné matematiky, kteří začínají používat tato zařízení jako spolupracovníky" při dokazování teorémů a podobně.

"Zajímavější pro mě je to, co nedokážou," řekl. "Jaké jsou limity tohoto typu počítače?" Jedním z těchto limitů je relativní nedostatek dat potřebných k trénování modelů AI pro některé problémy.

"Například navrhování nové matematické teorie, jako je relativita nebo Maxwellovy rovnice] - pro ty je mnohem méně příkladů, že? Takže si myslím, že tento typ teoretického průlomu bude pro tyto stroje těžší, protože neexistuje není tolik dat."

Vzhledem k mnoha důsledkům toho, že se P rovná nebo nerovná NP, je Wigderson spokojen s tím, že se nechá vést nová generace.

"Bavím se s postdoktorandy v ústavu a všichni jsou skvělí a s některými z nich spolupracuji a teprve se učím od mladých," řekl. "Je velmi příjemné být v této situaci obklopen mladými lidmi, která vás neustále učí."