Silná NP úplnost - Strong NP-completeness
Ve výpočetní složitosti je silná NP-úplnost vlastnost výpočetních problémů, což je speciální případ NP-úplnosti . Obecný výpočetní problém může mít numerické parametry. Například vstupem do problému sbalením koše je seznam objektů konkrétních velikostí a velikost košů, které musí objekty obsahovat - tyto velikosti objektů a velikost koše jsou číselné parametry.
Říká se, že problém je silně NP-úplný (NP-úplný v silném smyslu), pokud zůstane NP-úplný, i když jsou všechny jeho číselné parametry ohraničeny polynomem v délce vstupu. Říká se, že problém je silně NP-těžký, pokud má silně NP-úplný problém polynomiální redukci; zejména v kombinatorické optimalizaci je fráze „silně NP-tvrdá“ vyhrazena pro problémy, o nichž není známo, že mají polynomiální redukci na jiný silně NP-úplný problém.
Normálně jsou číselné parametry problému uvedeny v poziční notaci , takže problém vstupní velikosti n může obsahovat parametry, jejichž velikost je v n exponenciální . Pokud předefinujeme problém tak, aby parametry byly uvedeny v unární notaci , pak musí být parametry omezeny velikostí vstupu. Silnou NP-úplnost nebo NP-tvrdost lze tedy definovat jako NP-úplnost nebo NP-tvrdost této unární verze problému.
Například balení bin je silně NP-úplné, zatímco problém s batohem 0-1 je jen slabě NP-úplný . Tak verze bin balení, kde se objekt a bin velikosti jsou celá čísla ohraničené polynomiálních pozůstatky NP-úplný, zatímco odpovídající verze problému batohu může být řešen v pseudo-polynomiální čas od dynamického programování .
Z teoretického hlediska žádný silně NP-tvrdý optimalizační problém s polynomiálně ohraničenou objektivní funkcí nemůže mít plně polynomiálně-časové aproximační schéma (nebo FPTAS ), pokud P = NP. Konverzace však selže: např. Pokud se P nerovná NP, batoh se dvěma omezeními není silně NP-tvrdý, ale nemá FPTAS, i když je optimální cíl polynomiálně ohraničený.
Některé silně NP-úplné problémy mohou být v průměru stále snadno vyřešitelné , ale je pravděpodobnější, že v praxi dojde k obtížným instancím.
Silné a slabé NP-tvrdosti vs. silné a slabé algoritmy polynomiálního času
Za předpokladu P! = NP platí pro výpočetní problémy na celá čísla následující:
- Pokud je problém slabě NP-těžký , pak nemá slabě polynomiální časový algoritmus (polynomiální v počtu celých čísel a počtu bitů v největším celém čísle ), ale může mít pseudopolynomiální časový algoritmus (polynomiální v počtu celých čísel a velikost největšího celého čísla). Příkladem je problém s oddílem . Slabá NP-tvrdost i slabý polynomiální čas odpovídají kódování vstupních agentů v binárním kódování .
- Pokud je problém silně NP-těžký , pak nemá ani pseudo-polynomiální časový algoritmus. Rovněž nemá plně polynomiální časové aproximační schéma . Příkladem je problém se 3 oddíly . Jak silná NP-tvrdost, tak pseudo-polynomiální čas odpovídají kódování vstupních agentů v unárním kódování .