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


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

Porno insider: Jak virtuální realita vstupuje do filmů pro dospělé

Porno insider: Jak virtuální realita vstupuje do filmů pro dospělé

** Pornografie údajně představuje třetinu internetové obsahu a je technologický tahounem ** Do erotického obsahu postupně zasahuje i virtuální realita ** Kromě vizuálního vjemu se pracuje také na virtuálním uspokojení toho hmatového

Jan Dudek | 34

Jak je na tom baterie ve vašem notebooku? Otestujte si ji!

Jak je na tom baterie ve vašem notebooku? Otestujte si ji!

** Životnost akumulátorů není neomezená a jednoho dne přijde konec ** Otestovat stav baterie můžete pomocí celé řady nástrojů ** Případné problémy díky nim odhalíte dřív než bude pozdě

Karel Kilián | 20

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

Photolemur 3: Prostě do něj přetáhnete fotky a začne se dít magie. Tedy údajně...

** Je lepší nabušený Photoshop, nebo program s jedním tlačítkem? ** Photolemur si myslí to druhé ** Tento fotoeditor neumí skoro nic, a přitom (skoro) všechno

Jakub Čížek | 22

Miliardový večírek končí. Rusko nemůže být z Crew Dragonu nadšené

Miliardový večírek končí. Rusko nemůže být z Crew Dragonu nadšené

** USA platí Rusku stamiliony dolarů za dopravu astronautů na ISS ** Dopravu amerických astronautů mají nyní převzít soukromé lodě ** Rusko je vytlačováno ze hry, mohou ho spasit vesmírní turisté

Petr Kubala | 70

Co pořídit k počítači: tipy na osvědčené klávesnice, sluchátka a další příslušenství

Co pořídit k počítači: tipy na osvědčené klávesnice, sluchátka a další příslušenství

** Toto jsou tipy Živě.cz na příslušenství k počítači, se kterým neuděláte chybu ** Klávesnice, myši, tiskárny, sluchátka... ** Vybíráme jak příslušenství na běžnou práci, tak na hraní her

David Polesný | 26



Aktuální číslo časopisu Computer

Test 9 levných notebooků

Jak na digitalizaci fotek

Otestovali jsme chytré osobní váhy

Ohebné displeje: budoucnost či slepá cesta?