Problém P versus NP

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

[[Soubor:P np np-complete np-hard.png|thumb|260px|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>. == Související články == * [[NP (třída složitosti)]] == Reference == <references /> == Externí odkazy == * R. Impagliazzo, [http://cseweb.ucsd.edu/~russell/average.ps ''A personal view of average-case complexity''] ([[PostScript]]) {{Článek z Wikipedie}} [[Kategorie:Teoretická informatika]] [[Kategorie:Otevřené matematické problémy]] [[Kategorie:Problémy tisíciletí]]

Návrat na stránku „Problém P versus NP“.