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, Clay, Nejdůležitější otázka, Teoretická možnost, Kompletní znění, Bomba, Výpočetní model, Úloha, Prize, Stroj, Krátká vzdálenost, Páska, Bomb, Problém, Matematický problém


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

Kdyby měli železničáři tento superpočítač za 99 dolarů, nepotřebovali by lasery

Kdyby měli železničáři tento superpočítač za 99 dolarů, nepotřebovali by lasery

** Nejmodernější český železniční tunel je prošpikovaný technologiemi ** Za tři tisíce koupíte počítač, který je překoná ** Seznamte se s Nvidia Jetson Nano

Jakub Čížek | 50

Pojďme programovat elektroniku: České chytré zásuvky Netio pro kutily i firmy

Pojďme programovat elektroniku: České chytré zásuvky Netio pro kutily i firmy

** Wi-Fi zásuvky nevyrábí pouze Čína ** Vyzkoušeli jsme českou Netio PowerCable ** Je přímo určená pro vývojáře, má totiž jednoduché JSON API

Jakub Čížek | 43

Podívejte se, jak vypadá mikrofon nebo blecha pod elektronovým mikroskopem

Podívejte se, jak vypadá mikrofon nebo blecha pod elektronovým mikroskopem

** Z Brna pochází třetina světové produkce elektronových mikroskopů ** První československý kus vyrobila Tesla už v 50. letech ** Dnes na ni navazuje třeba brněnský Tescan

Jakub Čížek | 19

Windows 10 podle našich čtenářů: Poslali jste nám skoro 300 nápadů, jak je vylepšit

Windows 10 podle našich čtenářů: Poslali jste nám skoro 300 nápadů, jak je vylepšit

** Microsoft aktualizuje Windows 10 dvakrát ročně ** Jenže praktických novinek už není tolik jako dříve ** Poslali jste nám skoro 300 tipů, co by se měly Desítky ještě naučit

Jakub Čížek | 138



Aktuální číslo časopisu Computer

Speciál o přechodu na DVB-T2

Velký test herních myší

Super fotky i z levného mobilu

Jak snadno upravit PDF