Sciencemag.cz
Doporučujeme
David Gamarnik z MITu popsal novou metodiku, jak by se dalo přistupovat k problému P vs. NP, tedy otázce spadající do výpočetní složitosti, obou někde mezi informatikou a čistou matematikou. Otázka, zda P se může rovnat NP, patří mezi největší problémy současné matematiky, za jejich řešení vypsal Clayův matematický ústav milion dolarů (za každý).
V úloze jde o to, zda pro určitý typ problémů (tzv. NP úplné, asi nejznámější z nich je problém obchodního cestujícího) existuje algoritmus řešící je v polynomiálním čase (tj. čase polynomiálně rostoucím z závislosti na velikosti vstupu). Předpokládáme, že nikoliv, dokázat se to však zatím nikomu nepodařilo. Naopak v polynomiálním čase lze ověřit, zda předložené řešení je správné; z této asymetrie pak vyplývá např. i využití NP problémů v kryptografii a z toho se odvozující bezprostředně praktický význam této otázky. (Faktorizace ovšem mimochodem nepatří mezi NP úplné problémy, nebo se to alespoň nepředpokládá.) Nejde ale zdaleka jen o šifry, NP úplné problémy přímo souvisejí s řadou optimalizačních úloh, kdy hledáme maxima/minima určitých funkcí, respektive stavového prostoru. Na „univerzální“ algoritmus se při jejich řešení dnes obvykle rezignuje a spokojujeme se s algoritmy, který pro úlohu určitého typu dokážou najít dostatečně rychle dostatečně dobré řešení (lokální, nikoliv globální minimum/maximum). Právě zde se již uplatňují i kvantové počítače (tzv. kvantové žíhání).
Matematik Keith Devlin v také česky vyšlé knize Problémy pro třetí tisíciletí uváděl, že problém P vs NP by jako jedinou z příslušných „hlavních“ matematických hádanek mohl vyřešit i laik, kdyby dostal dobrý nápad. Nebo lze říct, že na rozdíl od ostatních úloh je tato pro laika celkem pochopitelná alespoň svým zadáním (:-)).
D. Gamarnik svou novou metodu přístupu k problému nazval overlap gap property (OGP), tedy nějak jako „vlastnost překrývání mezer“. V zásadě zde má jít o to, že reálné NP problémy by měly nejčastěji být nějak „náhodné“, příroda není škodolibá a neklade před nás ta nejobtížněji řešitelná zadání. Stačilo by nám tedy dokázat efektivně řešit tuto „náhodnou“ třídu NP problémů a samotnou otázku P vs. NP tak obejít.
Konkrétně se celá myšlenka demonstruje na zkoumání energetických hladin spinových skel. Nicméně snad si to lze představit obecně asi takto. Ve stavovém prostoru/adaptivní krajině (apod.) máme různá údolí a různé vrcholky. Hledáme maximum (viz úvodní obrázek).
Úlohu lze nejprve zjednodušit tím, že rozkrojíme hory v určité, předem stanovené výšce a budete ignorovat vše, co je pod touto mezní úrovní. Zbývá nám řada hor, přičemž každý bod na nich představuje potenciální řešení původního problému. Jak ukazuje obrázek, průměr jednotlivých vrcholků – píků – je obvykle mnohem menší než vzdálenost mezi nimi. Pokud bychom v této rozlehlé krajině vybrali dva libovolné body – dvě možná řešení – budou od sebe buď velmi blízko (pokud pocházejí ze stejné hory), nebo naopak velmi daleko (jsou-li z různých hor). „Mezera“ je buď malá, nebo velká, ale nic mezi tím.
Nové zjištění tvrdí, že tento stav, tedy OGP, se týká všech známých NP úplných problémů, které jsou „náhodné“. Výsledkem ale není zatím to, že by se pro tento typ úloh podařilo najít efektivní algoritmus, naopak se celou řadu algoritmů, které byly kandidáty, již podařilo vyloučit. Dokonce je možné, že se podaří dokázat, že P se nerovná NP – právě tímto způsobem, že dokážeme neexistenci efektivního algoritmu pro tuto řadu úloh (OGP); pak bude jasné, že už vůbec nemůže existovat ani algoritmus řešící v polynomiálním čase NP úplné úlohy obecně (naopak to platit ale nebude – OGP jsme se definovali tak, že nejde o ty nejobtížnější případy NP úplných úloh). Tedy ještě jinak řečeno: i náhodně vytvářené, „přirozené“ NP úplné problémy jsou hodně obtížné.
Prozatím se podařilo určit, že OGP nedokážou efektivně řešit tzv. stabilní algoritmy, tedy takové jejichž výstup se příliš nezmění, pokud se vstup změní jen málo. To platí nejen pro klasické, ale i pro kvantové počítače, respektive pro tzv. kvantové aproximační optimalizační algoritmy (quantum approximation optimization algorithms, QAOA).
David Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures, Proceedings of the National Academy of Sciences (2021). DOI: 10.1073/pnas.2108492118
Zdroj: Massachusetts Institute of Technology / Phys.org a další
