Problém P versus NP

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í.

[editovat] Popis tříd P a NP

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.

[editovat] Důsledky řešení

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í. Tyto 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 .

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.