Wikipedie

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

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
m popis Nedeterministického Turingova stroje
úpravy, drobné rozšíření (NTM nedělá žádné náhodné pokusy)
Řádek 1:
[[Soubor:P np np-complete np-hard.svg|thumb|Eulerův diagram tříd složitosti pro obě možnosti rozhodnutí tohoto problému]]
Jako '''problém P versus NP''' se v [[Teoretická informatika|teoretické informatice]] označuje otázka, zda platí [[rovnost (matematika)|rovnost]] [[P (třída složitosti)|P]] = [[NP (třída složitosti)|NP]]. Považuje se za nejdůležitější otevřený problém tohoto oboru a je zařazený mezi sedm tzv. [[Problémy tisíciletí|problémů tisíciletí]]. Třídy P a NP poprvé definoval americký informatik [[Stephen Cook]].
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í]].
 
== Popis tříd '''P''' a '''NP''' ==
[[Třída složitosti]] '''P''' obsahuje všechny úlohy, jejichž řešení lze nalézt [[Determinismusdeterminismus|deterministickým]] [[Turingův stroj|Turingovým strojem]] v [[Asymptotická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ý náhodnědokáže vybírásoučasně potenciálnítestovat řešenímnoho úlohymožností a v polynomiálním čase ověřuje jejich správnostř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. proMimo všechny [[NP-úplnost|NP-úplné]] problémy. Znamenalojiné by to znamenalo, že existují deterministické polynomiální (tedy „rychlé“) algoritmy na jejichřešení řešenívšech [[NP-úplnost|NP-úplných]] problémů. To by mělo zásadní dopad nejen na teoretickou informatiku, logiku,{{Fakt/dne|20100809132832}}, ale také filosofii{{Fakt/dne|20100809132832}} 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-úplnost|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 <math>P\neq NP</math>.
 
== Související články ==▼
{{Pahýl}}
* [[NP (třída složitosti)]]
 
== Externí odkazy ==
Dopad na logiku - otázka splnitelnosti pravdivostních formulí.
* R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps ''A personal view of average-case complexity''] ([[PostScript]])
 
[[Kategorie:Teoretická informatika]]
▲== Související ==
NP (třída složitosti) https://cs.wikipedia.org/wiki/NP-probl%C3%A9m[[Kategorie:Problémy tisíciletí]]
Citováno z „https://cs.wikipedia.org/wiki/Problém_P_versus_NP“