Dokáže generativní AI vyřešit největší nevyřešený problém počítačové vědy?

Otázka -- Má P=NP? -- je velká teoretická výzva. Vědci použili přístup myšlenek krmení lžičkou k GPT-4, aby hledali odpověď.

Počítačoví vědci přemýšlejí o tom, zda čas potřebný k výpočtu řešení není u těch nejtěžších problémů nedosažitelný. Otázka Má P=NP? je nyní považováno za relaci s několika výzvami s jazykovým modelem GPT-4. Největším náhledem na práci může být, jak oříznout minulé chatovací relace, aby se udržela diskuse.

Když počítačoví vědci tráví čas na koktejlových večírcích, mají tendenci si povídat mimo jiné o jediném nejdůležitějším nevyřešeném problému v informatice: otázce Je P=NP?

Otázka, zda se P rovná NP, formulovaná téměř před 50 lety, je hlubokou meditací o tom, čeho lze nakonec dosáhnout pomocí počítačů. Otázka, která má důsledky pro obory, jako je kryptografie a kvantové výpočty, navzdory desetiletím intenzivního studia odolávala přesvědčivé odpovědi. Nyní si toto úsilí vyžádalo pomoc generativní umělé inteligence.

V článku nazvaném „Large Language Model for Science: A Study on P vs. NP“ (Velký jazykový model pro vědu: Studie o P vs. NP) hlavní autor Qingxiu Dong a jeho kolegové programují velký jazykový model OpenAI GPT-4 pomocí toho, čemu říkají Sokratova metoda, několik cyklů chatu přes výzvu s GPT. -4. (Příspěvek byl tento měsíc zveřejněn na předtiskovém serveru arXiv vědci z Microsoftu, Pekingské univerzity, Beihang University v Pekingu a Pekingské technologické a obchodní univerzity.)

Metoda týmu se rovná přebírání argumentů z předchozího papíru a jejich podávání lžičkou do GPT-4, aby vyvolal užitečné odpovědi.

Dong a tým pozorují, že GPT-4 demonstruje argumenty k závěru, že P se ve skutečnosti nerovná NP. A tvrdí, že tato práce ukazuje, že velké jazykové modely dokážou více než vyplivnout obrovské množství textu, mohou také „objevit nové poznatky“, které mohou vést k „vědeckým objevům“, což je vyhlídka, kterou pokřtili „LLMs for Science“.

Abychom pochopili, co autoři dělají, je nutné vědět trochu o problému P=NP.

Problém P versus NP - neboli „P=NP“, jak je často označován - je otázkou, jak snadné je vyřešit daný problém. s počítačem. Písmeno P představuje problémy, které se ukázaly jako proveditelné k vyřešení, což znamená, že čas na výpočet řešení není mimo dosah; a jehož řešení lze také snadno ověřit, tedy zkontrolovat, zda je odpověď správná.

Písmena NP naproti tomu označují problémy, jejichž odpověď je také relativně snadno ověřitelná, stejně jako P, ale pro které není znám žádný snadný způsob, jak vypočítat řešení. Je běžné uvádět hru Sudoku jako příklad NP: jakákoliv vyplněná hra Sudoku může být docela snadno zkontrolována z hlediska přesnosti, ale úkol najít řešení roste exponenciálně, pokud jde o čas potřebný, jak se herní mřížka zvětšuje. (Pokud se chcete ponořit do těžkých teoretických detailů P=NP, zkuste Cookův dokument z roku 2000 o tomto problému.)

Problém tedy Je P=NP? ptá se, zda ty problémy, o kterých si myslíme, že je těžké vyřešit, NP, ale o kterých víme, že je lze snadno ověřit, by se ve skutečnosti mohly ukázat jako snadno ověřitelné a snadno řešitelné, stejně jako P problémy.

Negativní odpověď, že P se nerovná NP, by znamenala, že některé problémy jsou mimo schopnost počítačů vyřešit i s obrovskými výpočetními rozpočty - jinými slovy, horní hranice výpočetní techniky. Výzvy, jako je prolomení nějakého šifrování, by se pak zdály hrozivější, mimo dosah výpočetní techniky.

Aby se Dong a jeho tým vypořádali s P=NP, vycházeli z trendu posledních několika let „uvažování“ s velkými jazykovými modely. Jak dokládá práce Takeshi Kojimy a týmu z Tokijské univerzity a Google Research z roku 2022, je možné zlepšit schopnost velkých jazykových modelů na určitých úkolech jednoduše přidáním fráze „Pojďme přemýšlet krok za krokem“ na začátek výzva, doplněná příkladem odpovědi. Zjistili, že tato fráze byla dostatečná k tomu, aby vyvolala kroky „řetězce myšlenek“ na straně jazykového modelu.

Je to stejný typ myšlenkového postupu, který Dong a tým sledují se svou Sokratovou metodou. Prostřednictvím 97 rychlých kol autoři přemlouvají GPT-4 různými požadavky, které se dostanou do nejhrubšího z matematiky P=NP, a před každou z jejich výzev předloží úvodní prohlášení, které podmíní GPT-4, jako například: Jste moudrý filozof,“ „Jste matematik zběhlý v teorii pravděpodobnosti“ - jinými slovy, dnes již známá hra, jak přimět GPT-4, aby hrála roli, nebo „persona“, která stylizuje její generování textu.

Ukázka jednoho z chatovacích kol vysoce teoretické diskuse.

Jejich strategií je přimět GPT-4, aby dokázal, že P se ve skutečnosti nerovná NP, a to tak, že nejprve předpokládají, že tomu tak je, s příkladem a pak naleznou způsob, jak se tento příklad rozpadne - a přístup známý jako důkaz kontradikcí.

Zajímavé je, že dva z autorů výzkumu, Ke Xu a Guangyan Zhou, tento měsíc samostatně vydali článek, ve kterém přímo uvažují o P=NP v tradičních formálních matematických termínech. V tomto článku dochází k závěru, že P se nerovná NP.

To, co Dong a Xu a Zhou a tým dělají, se tedy podobá rekonstrukci jejich formální matematické práce tím, že vedou GPT-4 jazykem jejich vlastního uvažování, promptně. Ve skutečnosti ze 73stránkového papíru je 67 stran kompletním tiskem každé z 97 výzev a kompletní odpovědí z GPT-4. Je to jako obří cvičení rychlého inženýrství k rekonstrukci argumentu.

Těžko říci, zda výstup, kterého Dong a tým dosáhli s GPT-4, skutečně dokazuje, že P se nerovná NP, protože práce Xu a Zhoua je sama o sobě velmi nová. Na webu Semantic Scholar, který shromažďuje citace článků, zatím nejsou žádné citace pro tento článek - kromě jejich vlastního článku s Dongem a týmem. Existuje určitá diskuse o papíru GPT-4 různými zainteresovanými čtenáři na webu AI HuggingFace, který si můžete prohlédnout.

Svět tedy musí jejich argument ještě přijmout.

Pro lidi, kteří mají rádi Gen AI, je ještě důležitější, že autoři tvrdí, že jejich dialog ve výzvách ukazuje vyhlídky, že velké jazykové modely budou dělat víc než jen napodobovat lidské textové výtvory.

"Naše vyšetřování zdůrazňuje potenciální schopnost GPT-4 spolupracovat s lidmi při zkoumání výjimečně složitých problémů na expertní úrovni," píší. Na 67 stranách výzev a odpovědí zvýrazňují pasáže, které považují za „důležité části“ toho, co GPT-4 vyplivne.

To, jak zasvěcené jsou tyto odpovědi, je pravděpodobně také téma, které potřebuje vlastní prozkoumání. Někteří vědci zjistili, že velké jazykové modely jsou zvláště povrchní v tom, jak spojují citace a popisy.

Na okraji papíru se však objeví zajímavá výmluvná položka, kde Dong a tým komentují odpovědi GPT-4 svými postřehy o kvalitě odpovědí.

V jedné z těchto poznámek v závorkách autoři píší, že každá z předchozích odpovědí GPT-4 byla začleněna jako pozadí do poslední výzvy -- kromě kdy se autoři rozhodli ořezat odpovědi, aby zachovali pouze ty nejvíce relevantní bity.

„Pokud model poskytuje více řešení, zahrneme pouze to nejcennější řešení v historii konverzace,“ píší na okraj na straně 7. „Tato strategie umožňuje GPT-4 soustředit se na relevantní informace, čímž zvyšuje jeho celkovou efektivitu a efektivitu. ."

Jinými slovy, existovala určitá užitečná úprava způsobu, jakým GPT-4 používal minulou historii v tom, čemu se říká „kontextové okno“, ve všech předchozích kolech, ze kterých může čerpat. Dong a tým byli zapojeni do velmi selektivního rychlého inženýrství, aby provedli GPT-4 vláknem argumentu. To souvisí s praxí „generování rozšířeného vyhledávání“ nebo „RAG“, současný zájem o použití minulých dat chatu jako nového vstupu do velkého jazykového modelu.

To může být jeden z nejvýznamnějších příspěvků celého cvičení: Ať už to řeší P=NP, nebo ne, nová hranice v rychlém inženýrství by mohla posunout programy blíže k RAG, aby se chatovací relace dostaly na větší hloubku. . Když si vzpomenete na chatovací relace teprve nedávno, měli tendenci být hloupí a často se zatoulali mimo téma.

Během 97 kol se Dongovi a týmu podařilo udržet stroj na místě a k tomu je co říci.