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.

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?
Určitě si přečtěte

Jak vybrat monitor k počítači: nenechte se zlákat nepodstatnými parametry

Jak vybrat monitor k počítači: nenechte se zlákat nepodstatnými parametry

** Na jaké parametry se zaměřit a kde vás výrobci chtějí nachytat ** Monitory se stále více specifikují pro konkrétní určení ** Náročný hráč nebo profesionální grafik mají různé požadavky

20.  6.  2017 | Tomáš Holčík | 32

Dlouhodobý test HTC Vive: co vám recenze o virtuální realitě neřeknou

Dlouhodobý test HTC Vive: co vám recenze o virtuální realitě neřeknou

** Ani hry se sebelepší grafikou vás nevtáhnou tolik, jako ve virtuální realitě ** Pro sledování filmů není VR ani zdaleka ideální ** I první generace je skvělá, stále však působí jako prototyp

20.  6.  2017 | Stanislav Janů | 22

11 tipů, jak efektivně a přesně sledovat počasí pomocí internetu

11 tipů, jak efektivně a přesně sledovat počasí pomocí internetu

** Sledujte počasí z více zdrojů a podrobněji, přesněji tak určíte, jaké počasí vás potká na dovolené ** Na webu najdete hromadu pokročilých předpovědí počasí, ale i specializované meteorologické služby ** Vybrali jsme 14 služeb na počasí, které se vám můžou hodit

23.  6.  2017 | Jakub Čížek | 18

Jak unikají informace o nových iPhonech? Třeba podprsenkami čínských pracovnic

Jak unikají informace o nových iPhonech? Třeba podprsenkami čínských pracovnic

** Na černém trhu mohou zaměstnanci továren za kradené součástky inkasovat částku ve výši ročního platu ** Velké množství informací je vyneseno i z centrály Applu ** Díly jsou pašovány v botách, podprsenkách i odpadem

21.  6.  2017 | Stanislav Janů | 24


Aktuální číslo časopisu Computer

Bojujeme proti Fake News

Dva velké testy: fotoaparáty a NASy

Co musíte vědět o změně evropského roamingu

Radíme s výběrem základní desky