Informatická bomba. Problém P=NP vyřešen!

Informatická bomba. Problém P=NP vyřešen!

Pokud vám „problém P=NP“ nic neříká, patrně budete tuto bleskovku číst zcela zbytečně. Pokud naopak víte, o co jde, připravte se na skutečnou bombu. Jak se zdá, Vinay Deolalikar z HP Research Labs publikoval 6. srpna práci, která prokazuje, že P≠NP. Kompletní znění si můžete přečíst zde.

Pokud jste se s touto informací nespokojili, pokusím se stručně (a s nutnými zkratkami) vysvětlit, o co vlastně jde. Pod písmenem P se skrývá třída úloh, které umí deterministický Turingův stroj vyřešit v polynomiálním čase. Po NP pak třída úloh, jejichž řešení umí v polynomiálním čase ověřit (pozor, nikoliv vyřešit) také deterministický Turingův stroj, ale ono řešení umí v polynomiálním čase najít jen nedeterministický Turingův stroj. Je zřejmé, že P je podmnožinou NP, ale otázka, zda jsou tyto třídy úloh ekvivalentní, patří (či možná patřila) mezi nejdůležitější úlohy matematiky a informatiky. O její důležitosti svědčí i zařazení mezi sedm nejvýznačnějších matematických problémů tisíciletí (Millenim Prize Problems) podle Clay Mathematics Institute (více zde).

Turingův stroj

Pokud v informatice plavete natolik, že neznáte ani Turingův stroj, přijměte tento krátký popis. Turingův stroj je teoretickým základem informatiky; a základním (výpočetním) modelem počítače. Church-Turingovy teze říká, že jakýkoliv algoritmus jde popsat Turingovým strojem.

Vynecháme-li formální matematický popis, je Turingův stroj je tvořen „páskou“, na které jsou zapsána vstupní data, „čtecí hlavou“, která umí přečíst či zapsat právě jeden symbol a umí se na pásce posunout, a „stavy“, mezi kterými se celý stroj umí přepínat pomocí dané množiny přechodových funkcí. Výpočet Turingova stroje končí zamítnutím, přijetím, nebo zacyklením.

Nedeterministický Turingův stroj může mít po jeden stav a jeden symbol na pásce více vyhovujících přechodových funkcí, přičemž si mezi nimi vybere náhodně.
 

Pokud ani nyní netušíte, co by mělo být na problému P=NP tak světoborného, přijměte například příklad z kryptografie. Ta totiž v drtivé většině metod předpokládá, že šifry nejdou prolomit „dostatečně rychle“. Vychází přitom z toho, že čas potřebný pro jejich prolomení je větší, než polynomiální (vzhledem ke vstupním datům). Pokud by ale platilo, že P=NP, existovala by teoretická možnost rychlého prolamování šifrovacích algoritmů.

Ve skutečnosti důkaz P≠NP ukazuje, že třída NP-úplných úloh (nedeterministické polynomiální, na které jsou polynomiálně redukovatelné všechny ostatní NP úlohy) nejde řešit se stejnou složitostí, jako polynomiální úlohy – a to ani teoreticky.

Jestliže vám příklad z kryptografie nestačil, přidám asi nejslavnější NP-úplnou úlohu, tedy „problém obchodního cestujícího“. Zní přibližně takto: Je dána mapa se známými vzdálenostmi měst a úkolem je najít nejkratší cestu, která projde všechna města a vrátí se na start. Matematicky řečeno, je to úkol nalezení nejkratší hamiltonovské kružnice v úplném ohodnoceném grafu. Řešením je samozřejmě třeba hledání „všech možných cest“, ale cílem je najít nejefektivnější algoritmus. Pokud je důkaz Vinaye Deolalikara v pořádku, znamená to, že neexistuje algoritmus, který by problém obchodního cestujícího řešil v polynomiálním (či lepším, vzhledem k počtu měst) čase.

Diskuze (152) Další článek: O firemní sítě se často stará kde kdo, jen ne ajtíci

Témata článku: Technologie, Úloha, Kompletní znění, Clay, Krátká vzdálenost, Matematický problém, Problém, Zamítnutí, Páska, Stroj, Nejdůležitější otázka, Výpočetní model, Bomb, Bomba, Teoretická možnost, Prize


Určitě si přečtěte

Jak se žije s telefonem bez Googlu: Čerstvé zkušenosti s telefony Honor a Huawei

Jak se žije s telefonem bez Googlu: Čerstvé zkušenosti s telefony Honor a Huawei

** Honor u nás přichází s prvním telefonem bez Google Mobile Services ** Současný stav je lepší než na začátku, ideální ale není ** Zkusili jsme i hack s ručním přidáním služeb Googlu

Tomáš Holčík | 149

Teachable Machine: Umělá inteligence za pět minut i bez doktorátu z ČVUT

Teachable Machine: Umělá inteligence za pět minut i bez doktorátu z ČVUT

** Pochopit techniky a principy A.I. je složité ** Ale nebojte, jde to i bez doktorátu z IT a matematiky ** Vyzkoušíme generátor neuronových sítí od Googlu

Jakub Čížek | 10

Nové názvy, upravený vývoj. Microsoft ukázal, jak teď bude vydávat Windows 10

Nové názvy, upravený vývoj. Microsoft ukázal, jak teď bude vydávat Windows 10

** Podzimní vydání Windows 10 přinese jen minimum novinek ** Aktualizace ponese formální označení 20H2 ** Microsoft mění názvy v programu Windows Insider

Lukáš Václavík | 17

Z rozmazané šmouhy krásná fotka. Takhle kouzlí nová umělá inteligence MyHeritage

Z rozmazané šmouhy krásná fotka. Takhle kouzlí nová umělá inteligence MyHeritage

** MyHeritage slibuje nejlepší neuronovou síť pro vylepšování fotek ** Funguje tím líp, čím horší fotku upravuje ** Otestovali jsme desítky různých snímků

Marek Lutonský, Lukáš Václavík | 36

Apple má šanci definitivně se uzamknout. macOS byl na jeho poměry až příliš otevřený

Apple má šanci definitivně se uzamknout. macOS byl na jeho poměry až příliš otevřený

** Apple, vývojáře i uživatele rozhodně nečekají dva roky prázdnin ** macOS se může uzavřít podobně jako iOS a iPadOS ** Přechod na Arm znamená stopku pro hackintoshe

Lukáš Václavík | 102

Otestovali jsme nový Apple MacBook Air. S retinou a nižší cenou

Otestovali jsme nový Apple MacBook Air. S retinou a nižší cenou

** Test MacBooku Air v provedení pro rok 2020 ** Cenově dostupný notebook překvapí výkonem ** Výborné je celkové zpracování a klávesnice

Martin Miksa | 43


Aktuální číslo časopisu Computer

Megatest SSD s kapacitou 1 TB

Srovnávací test robotických vysavačů

Vybíráme nejlepší telefony na trhu

Jak zlepšit zvuk televize