NP obtížnost

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. července 2017; kontroly vyžadují 4 úpravy .

V teorii výpočetní složitosti je NP-tvrdost (nedeterministická časově-polynomická tvrdost) definující vlastností třídy problémů, které jsou neformálně „přinejmenším tak těžké jako nejtěžší problémy v NP “. Jednoduchým příkladem NP-těžkého problému je problém podmnožiny součtu .

Formální definice: Problém řešitelnosti je NP-těžký, pokud lze jakýkoli problém v NP redukovat v polynomiálním čase na . Ekvivalentní podmínka vyžaduje, aby každý problém v NP mohl být vyřešen v polynomiálním čase pomocí věštce pro [1] [2] . V důsledku toho algoritmus s polynomiálním časem pro řešení jakéhokoli NP-těžkého problému poskytne polynomiální algoritmy pro všechny problémy v NP.

Předpokládá se, že pro NP-obtížné problémy neexistují žádné polynomiální algoritmy, ale toto nebylo prokázáno (viz problém P≠NP ) [3] . Navíc třída P , ve které se všechny problémy řeší v polynomiálním čase, je obsažena ve třídě NP [4] .

Některé NP-tvrdé optimalizační problémy mohou být polynomiálně aproximovány k nějakému konstantnímu (konstantnímu) aproximačnímu faktoru (zejména v APX ) nebo dokonce k jakémukoli aproximačnímu faktoru (v PTAS nebo FPTAS ).

Názvy tříd v tvrdosti NP

NP těžké problémy nemusí být prvky třídy složitosti NP. Protože třída NP je klíčovou třídou v teorii výpočetní složitosti , používá se jako základ pro následující třídy:

NP Třída výpočetních rozhodovacích problémů, pro které může být jakékoli dané kladné rozhodnutí ověřeno jako řešení v polynomiálním čase deterministickým Turingovým strojem (nebo vyřešeno nedeterministickým Turingovým strojem v polynomiálním čase). NP-hard (NP-hard) Třída problémů, které nejsou o nic méně obtížné než nejtěžší problémy v NP. Problémy, které jsou těžké NP, nemusí být prvky NP; ve skutečnosti mohou být takové problémy dokonce neřešitelné. NP-úplný (NP-úplný) Třída problémů řešitelnosti, která obsahuje nejtěžší problémy v NP. Každý NP-úplný problém musí být v NP a redukován na jakýkoli jiný NP-úplný problém. NP-intermediate (NP-intermediate) Třída středních úloh řešitelnosti mezi P a NP-úplné, za předpokladu, že třídy P a NP jsou různé. (Pokud P=NP, pak neexistují žádné NP-střední, protože každý problém z NP (a P) se v tomto případě redukuje na NP-úplné, které zase v tomto případě leží v NP a tedy v P)

Příklady

Problém součtu podmnožin : Má daná množina celých čísel neprázdnou podmnožinu, která se rovná nule? Toto je problém řešitelnosti a je NP-úplný.

Problém cestujícího obchodníka je optimalizační problém nalezení cyklické trasy s nejnižšími náklady přes všechny uzly váženého grafu. Toto je NP-těžký problém [5] .

Problém zastavení je problém, který je NP-těžký, ale není NP-úplný. Úkol zní: "S ohledem na program a jeho vstup, zastaví se program?" Je snadné dokázat, že problém zastavení je NP-těžký, ale ne NP-úplný – booleovský problém splnitelnosti lze zredukovat na problém zastavení tím, že jej převedete na popis Turingova stroje , který zkouší všechny možné vstupy, a když se najde ten, který splňuje vzorec, zastaví se, jinak vstoupí do nekonečné smyčky. Také problém zastavení není obsažen v NP, protože všechny problémy v NP jsou řešitelné v konečném počtu operací a problém zastavení je nerozhodnutelný .

Existují NP-těžké problémy, které nejsou ani NP-úplné, ani nerozhodnutelné . Například jazyk pravdivých kvantifikovaných booleovských vzorců je rozhoditelný v polynomiálním prostoru , ale ne v nedeterministickém polynomiálním čase (pokud je NP ≠ PSPACE pravdivý ) [6] .

Aplikace

NP-těžké problémy se nejčastěji vyskytují v oblastech, jako jsou:

Poznámky

  1. ↑ Příručka teoretické informatiky. - Amsterdam: Elsevier, 1998. - Sv. A, Algoritmy a složitost. — ISBN 0262720140 .
  2. ↑ Knuth, Donald (1974). Postscript o NP-těžkých problémech. Novinky ACM SIGACT . 6 (2): 15-16. DOI : 10.1145/1008304.1008305 .
  3. ↑ Shtetl-Optimized » Archiv blogu » Vědecký případ pro P≠NP . www.scottaaronson.com . Staženo: 25. září 2016.
  4. ↑ PHYS771 Přednáška 6: P, NP a přátelé . www.scottaaronson.com . Staženo: 25. září 2016.
  5. ↑ Lawler, E.L .; Lenstra, JK ; Rinnooy Kan, AHG & Shmoys, D.B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization , John Wiley & Sons, ISBN 0-471-90413-9 , < https://archive.org/details/travelingsalesma00lawl >  .
  6. ↑ Přesněji řečeno, tento jazyk je PSPACE-complete ; viz Wegener, Ingo (2005), Teorie složitosti: Exploring the Limits of Efficient Algorithms , Springer, str. 189, ISBN 9783540210450 , < https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189 >  .