Problém P versus NP: Porovnání verzí

Jako '''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é rychle vyřešit. Všeobecně se předpokládá, že platí '''P''' ≠ '''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í]].

 

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