Zobrazení zdroje stránky Problém P versus NP

[[Soubor:P np np-complete np-hard.svg|náhled|Eulerův diagram tříd složitosti pro obě možnosti rozhodnutí tohoto problému]]
'''Problém P versus NP''' je důležitý otevřený problém v [[teoretická informatika|teoretické informatice]]; označuje se tak otázka, zda jsou [[třída složitosti|třídy složitosti]] '''[[P (třída složitosti)|P]]''' a '''[[NP (třída složitosti)|NP]]''' totožné. Zjednodušeně řečeno jde o otázku, zda každý problém, u kterého dokáže počítač rychle ověřit správnost nabídnutého řešení, dokáže počítač také sám rychle vyřešit. Všeobecně se předpokládá, že platí '''P'''&nbsp;≠&nbsp;'''NP''', tedy že existují úlohy, které je složitější vyřešit než ověřit platnost řešení. [[Matematický důkaz|Důkaz]] však stále nebyl nalezen a tento problém je zařazený mezi sedm tzv. [[problémy tisíciletí|problémů tisíciletí]].

== Popis tříd P a NP ==
[[Třída složitosti]] '''P''' obsahuje všechny úlohy, jejichž řešení lze nalézt [[determinismus|deterministickým]] [[Turingův stroj|Turingovým strojem]] v [[asymptotická složitost|polynomiálním]] čase.

Pro třídu '''NP''' platí totéž s tím rozdílem, že úlohy jsou v polynomiálním čase řešitelné hypotetickým ''nedeterministickým'' Turingovým strojem, který dokáže současně testovat mnoho možností řešení. Jsou to tedy 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''.

Třídy '''P''' a '''NP''' poprvé definoval americký informatik [[Stephen Cook]].

== Důsledky řešení ==
Platí-li '''P''' = '''NP''', má to dalekosáhlé důsledky. Mimo jiné by to znamenalo, že existují deterministické polynomiální (tedy „rychlé“) algoritmy na řešení všech [[NP-úplnost|NP-úplných]] problémů. To by mělo zásadní dopad nejen na teoretickou informatiku, logiku, ale také filosofii<ref>http://www.scottaaronson.com/papers/philos.pdf - Why Philosophers Should Care About Computational Complexity</ref> a zejména [[kryptografie|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ů<ref>http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf - SIGACT News Complexity Theory Column 74</ref> přesvědčena o tom, že rovnost neplatí, tedy že <math>P\neq NP</math>.

== Reference ==
<references />

== Související články ==
* [[NP (třída složitosti)]]

== Externí odkazy ==
* R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps ''A personal view of average-case complexity''] ([[PostScript]])

[[Kategorie:Teoretická informatika]]
[[Kategorie:Problémy tisíciletí]]