Rovnost tříd P a NP

Otázka rovnosti tříd složitosti P a NP (známá v ruských zdrojích také jako problém výčtu [1] [2] ) je jedním z ústředních otevřených problémů v teorii algoritmů již více než tři desetiletí. Pokud na něj bude dána kladná odpověď, bude to znamenat, že je teoreticky možné vyřešit mnoho složitých problémů mnohem rychleji než nyní.

Vztahem mezi třídami P a NP se zabývá odvětví teorie algoritmů zvané teorie výpočetní složitosti . Studuje zdroje potřebné k vyřešení nějakého problému. Nejběžnějšími zdroji jsou čas (kolik kroků je třeba udělat) a paměť (kolik paměti je potřeba k dokončení úkolu).

Problém rovnosti tříd P a NP je jedním ze sedmi problémů tisíciletí , za které Clay Mathematical Institute udělil cenu ve výši jednoho milionu amerických dolarů .

Formulace

Volně řečeno, problém rovnosti P = NP je následující: pokud lze kladnou odpověď na nějakou otázku zkontrolovat poměrně rychle (v polynomiálním čase ), pak je pravda, že odpověď na tuto otázku lze nalézt poměrně rychle (také v polynomu čas a pomocí polynomiální paměti )? Jinými slovy, opravdu není snazší ověřit si řešení problému, než ho najít? [3]

Je například pravda, že mezi čísly { −2 , −3 , 15 , 14 , 7 , −10 , …} jsou taková, že jejich součet je roven 0 ( problém podmnožinových součtů )? Odpověď je ano , protože −2 −3 + 15 −10 = 0 lze snadno ověřit několika dodatky (informace potřebné k ověření kladné odpovědi se nazývá certifikát ). Z toho plyne, že je stejně snadné získat tato čísla? Je kontrola certifikátu stejně snadná jako jeho nalezení? Zdá se, že vyzvednutí čísel je obtížnější, ale není to prokázáno.

Z definice tříd P a NP bezprostředně plyne důsledek: . O přísnosti tohoto zařazení, tedy zda existuje problém, který spočívá v NP , ale neleží v P , není zatím nic známo. Pokud takový problém neexistuje, pak lze všechny problémy patřící do třídy NP vyřešit v polynomiálním čase, což slibuje obrovský přínos ve výpočetní rychlosti. Nyní lze nejsložitější problémy ze třídy NP (tzv. NP - complete problems ) řešit v exponenciálním čase, což je z praktického hlediska považováno za nepřijatelné.

Historie

Otázku výpočetní složitosti pravděpodobně poprvé položil Kurt Gödel v roce 1956 v dopise Johnu von Neumannovi , kde se zeptal, zda by problém (nyní známý jako NP-úplný) mohl být vyřešen v kvadratickém nebo lineárním čase. Gödel zároveň navrhl, že pokud řešení existuje, pak to umožní počítačům řešit mnoho matematických problémů [4] .

Otázku třídní rovnosti poprvé nastolil Stephen Cook v roce 1971 [5] a nezávisle na tom Leonid Levin v roce 1973 [6] .

Na začátku roku 2000 většina matematiků věří, že tyto třídy nejsou stejné. Podle průzkumu provedeného v roce 2002 mezi 100 vědci [7] 61 lidí věří, že odpověď je „nerovná se“, 9 – „rovná se“, 22 bylo obtížné odpovědět a 8 se domnívá, že hypotézu nelze odvodit ze současné systém axiomů , a proto jej nelze dokázat ani vyvrátit.

Stejně jako jiné známé nevyřešené matematické problémy, i pokusy o vyřešení tohoto problému vyžadují značné úsilí; chybné důkazy o rovnosti či nerovnosti tříd P a NP jsou pravidelně publikovány (nikoli ve vědecké literatuře), obvykle laiky [8] .

Ochranné systémy, které předpokládají nerovnost tříd P a NP

Jakýkoli kryptosystém s veřejným klíčem je založen na předpokladu existence jednosměrných funkcí a/nebo extrémního trvání řešení určitého problému (např. pro algoritmus RSA se jedná o faktorizaci velmi velkých čísel).

K ochraně počítačových systémů před zneužitím služeb je požadující strana požádána, aby vyřešila problém, jehož řešení zabere mnoho času, a výsledek je snadno a rychle zkontrolován obsluhující stranou. Příkladem takovéto antispamové ochrany je systém Hashcash [9] , který při odesílání e-mailů používá hash částečné inverze.

Blockchainy založené na technologii proof-of-work vyžadují, aby výsledný hash součet byl nižší než cílová hodnota. Proces hledání požadovaného hash součtu vyžaduje jeho opakovaný přepočet s výčtem libovolných hodnot doplňkového parametru (podrobněji viz Mining ). Všechny počítače v systému tráví značné množství času hledáním jednoho uspokojivého hash součtu (například v bitcoinu je to v průměru 10 minut pro každého z těžařů ). Pro kontrolu správnosti již vytvořeného bloku je zapotřebí pouze jeden výpočet hash.

Podobné problémy

Viz také

Poznámky

  1. ↑ A. A. Razborov. P ?= NP aneb problém výčtu: pohled z 90. let .
  2. ↑ A. H. Shen . Problém výčtu  // PostNauka .
  3. ↑ Stuart, 2015 , str. 291.
  4. ↑ Hartmanis, Juris. Gödel, von Neumann a problém P = NP  (neopr.)  // Bulletin Evropské asociace pro teoretickou informatiku. - T. 38 . - S. 101-107 .
  5. ↑ Stephen Cook. Význam otázky P versus NP Archivováno 9. července 2011 na Wayback Machine .
  6. ↑ L. A. Levin. Univerzální enumerační  problémy // Problémy přenosu informací. - 1973. - T. 9 , č. 3 . - S. 115-116 .
  7. ↑ Vilém I. Gasarch. Průzkum P=?NP  (neopr.)  // Zprávy SIGACT. - 2002. - T. 33 , č. 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
  8. ↑ Lenta.ru – minulost. Matematici nakonec ztratili víru v řešení problému tisíciletí . Získáno 26. srpna 2010. Archivováno z originálu 30. srpna 2010.
  9. ↑ Hashcash – A Denial of Service Counter-Measure (2002)
  10. ↑ Razborov, 2016 , str. 24.
  11. ↑ MIP* = RE: Důkaz v počítačové vědě, který způsobil dominový efekt ve fyzice a matematice / Blog RUVDS.com / Sudo Null IT News . Získáno 24. prosince 2020. Archivováno z originálu dne 12. května 2021.
  12. ↑ [https://web.archive.org/web/20210119084755/https://arxiv.org/abs/2001.04383 Archivováno 19. ledna 2021 na Wayback Machine [2001.04383] MIP*=RE]

Literatura

Odkazy

  Přejděte na položku Wikidata  Slovníky a encyklopedie