Problém P versus NP - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

2022-08-14T14:53:16Z

Nahrazení textu „</math>“ textem „\)</big>“

← Starší verze		Verze z 14. 8. 2022, 14:53
Řádka 10:		Řádka 10:

	== Důsledky řešení ==		== 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 <big>\(P\neq NP</~~math~~>.	+	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 <big>$P\neq NP$</big>.

	== Související články ==		== Související články ==

Sysop: Nahrazení textu „ $“ textem „$ \(“

2022-08-14T14:49:52Z

Nahrazení textu „<math>“ textem „<big>\(“

← Starší verze		Verze z 14. 8. 2022, 14:49
Řádka 10:		Řádka 10:

	== Důsledky řešení ==		== 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>.	+	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 <big>\(P\neq NP</math>.

	== Související články ==		== Související články ==

Sysop: + Nový článek

2019-03-03T10:32:43Z

+ Nový článek

Nová stránka

[[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''' ≠ '''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í]]

Problém P versus NP - Historie editací

Sysop: Nahrazení textu „“ textem „\)“

Sysop: Nahrazení textu „“ textem „\(“

Sysop: + Nový článek

Sysop: Nahrazení textu „ $“ textem „$ \(“