reklama

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.

Témata článku: Technologie, Clay, Prize, Bomb

152 komentářů

Nejnovější komentáře

  • Dany0 14. 8. 2010 16:07:53
    Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt,...
  • Marv-CZ 12. 8. 2010 14:38:32
    No vidíte, to máte stejné jako s tou Vaší Biblí. Ta je také každým a...
  • jehoVista 11. 8. 2010 23:48:58
    Treba to jednou vyjde a proc by to treba nemohlo byt ted?
reklama
Určitě si přečtěte

Vybíráte herní periferii nebo hardware? Pak zapomeňte na nálepku Gaming

Vybíráte herní periferii nebo hardware? Pak zapomeňte na nálepku Gaming

** Herní hardware se od toho běžného často liší jen vzhledem ** Při výběru stále nezapomínejte na základní parametry ** Poradíme jak vybrat herní hardware i periferie

20.  2.  2017 | Stanislav Janů | 36

10 nejhorších produktů v historii Microsoftu

10 nejhorších produktů v historii Microsoftu

20.  2.  2017 | Karel Javůrek | 141

AMD oficiálně představilo procesory Ryzen. Známe i jejich české ceny

AMD oficiálně představilo procesory Ryzen. Známe i jejich české ceny

** AMD uvedlo první tři procesory Ryzen 7 ** Všechny budou pracovat s osmi jádry a šestnácti vlákny ** Na pulty obchodů se dostanou už za týden

22.  2.  2017 | Stanislav Janů | 133

EU se děsí Windows 10. Prý o nás vědí až příliš. Microsoft chystá změny

EU se děsí Windows 10. Prý o nás vědí až příliš. Microsoft chystá změny

** Evropští úředníci chtějí, aby byly Desítky transparentnější ** Microsoft od jara skutečně chystá změny ** Ochráncům soukromí to ale nestačí

21.  2.  2017 | Jakub Čížek | 218

Remix Singularity: Microsoft si na tom vylámal zuby. Jak dopadne Android?

Remix Singularity: Microsoft si na tom vylámal zuby. Jak dopadne Android?

** Microsoft do svých telefonů integroval desktopové prostředí ** Moc to ale nevyšlo, chyběl pořádný výkon ** Teď to zkoušejí ex-googleři s Remix Singularity

23.  2.  2017 | Jakub Čížek | 74


Aktuální číslo časopisu Computer

Supertéma o počítačové bezpečnosti

AMD Ryzen přichází

Velké testy kinoprojektorů a levných špuntových sluchátek

Příslušenství do USB-C

reklama
reklama