Problém P versus NP

Technology

12 hours ago

Author

Problém P versus NP je jedním z nejvýznamnějších problémů teorie složitosti v informatice. Sporný je otázkou, zda je těžké problémy možné efektivně vyřešit. Tento problém má přímý vliv na mnoho oblastí informatiky, jako je kryptografie, algoritmická teorie, optimalizace a mnoho dalších. Problém P versus NP se ptá, zda jsou problémy P (složitostní třída problémů, které jsou efektivně řešitelné na deterministickém Turingově stroji) ekvivalentní s problémy NP (složitostní třída problémů, které jsou řešitelné deterministickým Turingovým strojem s nedeterminismem). Pokud by se ukázalo, že problém P je ekvivalentní s problémem NP, znamenalo by to, že pro každý problém s existujícím řešením existuje algoritmus, který ho vyřeší efektivně. Naopak, pokud by se ukázalo, že problém P není ekvivalentní s problémem NP, znamenalo by to, že existují problémy, které nejsou možné řešit efektivně. Řešení problému P versus NP má velký význam v mnoha vědeckých disciplínách, kde se setkáváme s problémy, které jsou obtížně řešitelné. Dosud se však nepodařilo prokázat ani vyvrátit platnost hypotézy P versus NP a zůstává jedním z nejdůležitějších otevřených problémů teorie složitosti.

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é informatice; označuje se tak otázka, zda jsou třídy složitosti P a 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í. Důkaz však stále nebyl nalezen a tento problém je zařazený mezi sedm tzv. 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 deterministickým Turingovým strojem v 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-úplných problémů. +more To by mělo zásadní dopad nejen na teoretickou informatiku, logiku, ale také filosofii a zejména 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ů přesvědčena o tom, že rovnost neplatí, tedy že P\neq NP.