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

Platí-li '''P''' = '''NP''', má to dalekosáhlé důsledky pro všechny [[NP-úplnost|NP-úplné]] problémy. Znamenalo by to, že existují deterministické polynomiální (tedy „rychlé“) algoritmy na jejich řešení. 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>.