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

Špičkoví hackeři útočili na prohlížeče. Chrome odolal, ale Edge je tragédie

Špičkoví hackeři útočili na prohlížeče. Chrome odolal, ale Edge je tragédie

** Do Vancouveru se sjeli hackeři ** Soutěžili v útocích na prohlížeče ** Chrome odolal, ale Edge to projel na celé čáře

22.  3.  2017 | Jakub Čížek | 79

Pojďme programovat elektroniku: Meteostanice, která bude díky Sigfoxu posílat stav počasí třeba z vrcholu Sněžky

Pojďme programovat elektroniku: Meteostanice, která bude díky Sigfoxu posílat stav počasí třeba z vrcholu Sněžky

** Příští roky budou ve znamení internetu věcí ** Podívali jsme se podrobně na síť Sigfox ** Takhle s ní komunikují krabičky z celé Evropy

19.  3.  2017 | Jakub Čížek | 18

Kde nejlevněji uložit 1 TB dat: Srovnali jsme aktuální ceny cloudových úložišť

Kde nejlevněji uložit 1 TB dat: Srovnali jsme aktuální ceny cloudových úložišť

** Srovnali jsme známá cloudová úložiště podle toho, kolik měsíčně zaplatíte za 1TB ** Ceny se pohybují od dvou stovek až po tisíc korun ** Google umožní uložit až 30 TB dat

18.  3.  2017 | Stanislav Janů | 115

Obří Mechroboti jsou realitou, měří čtyři metry a mají hmotnost přes 1,5 tuny

Obří Mechroboti jsou realitou, měří čtyři metry a mají hmotnost přes 1,5 tuny

** Jihokorejská společnost Hankook Mirae Technology vyrábí obří Mechroboty ** Jsou určené pro ovládání člověkem uvnitř ** V prodeji se objeví koncem tohoto roku za 200 milionů korun

20.  3.  2017 | Karel Javůrek | 18

Google představil nový Android O. Na co se můžeme těšit?

Google představil nový Android O. Na co se můžeme těšit?

** Google vypustil vývojářskou verzi nového Androidu ** Přinese lepší notifikace nebo prodlouženou výdrž ** K uživatelům se dostane na podzim

22.  3.  2017 | Stanislav Janů | 60


Aktuální číslo časopisu Computer

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

AMD Ryzen přichází

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

Příslušenství do USB-C