Problém P versus NP

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Jako problém P versus NP se v teoretické informatice označuje otázka, zda platí rovnost P = NP. Považuje se za nejdůležitější otevřený problém tohoto oboru a je zařazený mezi sedm tzv. problémů tisíciletí. Třídy P a NP poprvé definoval americký informatik Stephen Cook.

Popis tříd P a NP[editovat | editovat zdroj]

Třída složitosti P obsahuje všechny úlohy, jejichž řešení lze nalézt deterministickým Turingovým strojem v polynomiálním čase. Pro třídu NP platí totéž s tím rozdílem, že se jedná o nedeterministický Turingův stroj. Jsou to ty problémy, jejichž řešení lze ověřit v polynomiálním čase, ovšem nevíme, zda je lze také v polynomiálním čase nalézt.

Důsledky řešení[editovat | editovat zdroj]

Platí-li P = NP, má to dalekosáhlé důsledky pro všechny NP-úplné problémy. Znamenalo by to, že existují deterministické polynomiální (tedy „rychlé“) algoritmy na jejich řešení. To by mělo zásadní dopad nejen na teoretickou informatiku, logiku[zdroj?], ale také filosofii[zdroj?] a zejména kryptografii. Obtížnost prolomení řady moderních šifer, které se dnes každodenně používají, totiž závisí na předpokladu, že platí nerovnost. NP-úplné problémy − mezi něž patří důležité praktické úlohy, jako např. problém obchodního cestujícího − jsou považovány za „těžké“ a předpokládá se, že žádný takový efektivní algoritmus pro ně neexistuje. To je také hlavní důvod, proč je dnes většina odborníků přesvědčena o tom, že rovnost neplatí, tedy že P\neq NP.

Dopad na logiku - otázka splnitelnosti pravdivostních formulí.