NP-tvrdost - NP-hardness

Jemnější úvod viz problém P versus NP .
Eulerův diagram pro P, NP, NP-kompletní a NP-tvrdou sadu problémů.
Eulerův diagram pro P , NP , NP-kompletní a NP-tvrdou sadu problémů. Levá strana je platná za předpokladu, že P ≠ NP , zatímco pravá strana je platná za předpokladu, že P = NP (kromě toho, že prázdný jazyk a jeho doplněk nikdy nejsou úplné)

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

Přesnější specifikace je: problém H je NP-tvrdý, když každý problém L v NP může být redukován v polynomiálním čase na H ; to znamená, za předpokladu, že řešení pro H trvá 1 jednotku času, může být H řešení použito k řešení L v polynomiálním čase. V důsledku toho by nalezení polynomiálního časového algoritmu k vyřešení jakéhokoli NP-tvrdého problému poskytlo polynomiální časové algoritmy pro všechny problémy v NP. Jelikož existuje podezření, že P NP , je nepravděpodobné, že takový algoritmus existuje.

Běžná mylná představa je, že NP v „NP-hard“ znamená „nepolynomiální“, i když ve skutečnosti znamená „ nedeterministické polynomiální přijatelné problémy“. Je podezření, že neexistují žádné algoritmy polynomiálního času pro NP-hard problémy, ale to se neprokázalo. Navíc třída P , ve které lze vyřešit všechny problémy v polynomiálním čase, je obsažena ve třídě NP .

Definice

Rozhodnutí problém H je NP-těžké, když pro každý problém L v NP, existuje polynomiální redukce mnoho-jedna z L do H . Ekvivalentní definice je požadavek, aby každý problém L v NP může být řešen v polynomial čase pomocí Oracle stroj s věštce pro H . Neformálně lze uvažovat o algoritmu, který volá takový věštecký stroj jako podprogram pro řešení H a řeší L v polynomiálním čase, pokud výpočet podprogramu trvá jen jeden krok.

Další definice je požadavek, aby se ke snížení polynomiální z NP-úplný problém G až H . Protože jakýkoli problém L v NP se redukuje v polynomiálním čase na G , L se zase redukuje na H v polynomiálním čase, takže tato nová definice implikuje předchozí. Nešikovně neomezuje problémy třídy NP-hard na problémy s rozhodováním a zahrnuje také problémy s vyhledáváním nebo optimalizací .

Důsledky

Pokud P ≠ NP, pak NP-tvrdé problémy nemohly být vyřešeny v polynomiálním čase.

Některé problémy s optimalizací NP-hard mohou být aproximovány v polynomiálním čase až do nějakého konstantního aproximačního poměru (zejména u APX ) nebo dokonce až do jakéhokoli aproximačního poměru (u PTAS nebo FPTAS ).

Příklady

Příkladem NP-těžkého problému je problém se součtem podmnožiny rozhodnutí : je-li dána množina celých čísel, přidává se nějaká neprázdná podmnožina z nich na nulu? To je problém s rozhodnutím a je náhodou NP-úplný. Dalším příkladem NP-těžkého problému je optimalizační problém hledání nejméně nákladné cyklické trasy přes všechny uzly váženého grafu. To se běžně označuje jako problém obchodního cestujícího .

Existují problémy s rozhodováním, které jsou NP-tvrdé, ale ne NP-úplné , jako je problém se zastavením . To je problém, který se ptá „vzhledem k danému programu a jeho vstupu, bude fungovat navždy?“ To je otázka ano / ne, stejně jako rozhodovací problém. Je snadné dokázat, že problém se zastavením je NP-tvrdý, ale ne NP-úplný. Například problém s Booleovskou uspokojivostí lze snížit na problém se zastavením jeho transformací na popis Turingova stroje, který zkouší všechna přiřazení hodnot pravdy, a když najde takový, který splňuje vzorec, zastaví se a jinak se dostane do nekonečné smyčky. Je také snadné vidět, že problém zastavení není v NP, protože všechny problémy v NP jsou rozhodnutelné v konečném počtu operací, ale problém zastavení je obecně nerozhodnutelný . Existují také NP-tvrdé problémy, které nejsou NP-úplné ani nerozhodnutelné . Například jazyk skutečných kvantifikovaných booleovských vzorců je rozhodnutelný v polynomiálním prostoru , ale ne v nedeterministickém polynomiálním čase (pokud NP = PSPACE ).

Konvence pojmenování NP

NP-tvrdé problémy nemusí být prvky třídy složitosti NP. Protože NP hraje ústřední roli ve výpočetní složitosti , používá se jako základ několika tříd:

NP
Třída výpočetních rozhodovacích problémů, pro něž nějaký daný ano -roztokem lze ověřit ve formě roztoku v polynomiálním čase deterministický Turing stroj (nebo řešitelné prostřednictvím non-deterministický Turing stroj v polynomiálním čase).
NP-tvrdé
Třída problémů, které jsou přinejmenším stejně těžké jako nejtěžší problémy v NP. Problémy, které jsou NP-tvrdé, nemusí být prvky NP; ve skutečnosti nemusí být ani rozhodnutelné.
NP-kompletní
Třída rozhodovacích problémů, která obsahuje nejtěžší problémy v NP. Každý NP-úplný problém musí být v NP.
NP-snadné
Maximálně tak tvrdý jako NP, ale ne nutně v NP.
NP-ekvivalent
Problémy s rozhodováním, které jsou NP-tvrdé i NP-snadné, ale ne nutně v NP.
NP-střední
Pokud se P a NP liší, pak existují problémy s rozhodováním v oblasti NP, které spadají mezi P a NP-úplné problémy. (Pokud P a NP jsou stejné třídy, pak NP-přechodné problémy neexistují, protože v tomto případě by každý NP-úplný problém spadl do P, a podle definice může být každý problém v NP redukován na NP-úplný problém. )

Oblasti použití

Problémy NP-hard se často řeší pomocí jazyků založených na pravidlech v oblastech, jako jsou:

Reference