Silná NP úplnost - Strong NP-completeness

v výpočetní složitost, silná NP úplnost je vlastnost výpočetních problémů, což je zvláštní případ NP-úplnost. Obecný výpočetní problém může mít numerické parametry. Například vstup do balení koše problémem je seznam objektů konkrétních velikostí a velikost přihrádek, které musí obsahovat objekty - tyto velikosti objektů a velikost přihrádky jsou numerické parametry.

Problém se říká, že je silně NP-kompletní (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.[1] Problém se říká, že je silně NP-tvrdé 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 kterých 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í notace, takže problém s velikostí vstupu n může obsahovat parametry, jejichž velikost je exponenciální vn. Pokud předefinujeme problém tak, aby byly uvedeny parametry unární notace, pak musí být parametry omezeny velikostí vstupu. Silnou NP-úplnost nebo NP-tvrdost lze tedy také definovat jako NP-úplnost nebo NP-tvrdost této unární verze problému.

Například, balení koše je silně NP-kompletní, zatímco 0-1 Problém s batohem je pouze slabě NP-kompletní. Verze balení koše, kde jsou velikost objektu a zásobníku celá čísla ohraničená polynomem, tedy zůstává NP-úplná, zatímco odpovídající verzi problému s batohem lze vyřešit v pseudo-polynomiální čas podle dynamické 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 a schéma plně polynomiálního času (nebo FPTAS ) pokud P = NP.[2][3] Konverzace však selže: např. pokud P se nerovná NP, batoh se dvěma omezeními není silně NP-tvrdý, ale nemá FPTAS, i když je optimální objekt polynomiálně ohraničený.[4]

Některé silně NP-úplné problémy mohou být stále snadno vyřešitelné v průměru, ale je pravděpodobnější, že se v praxi setkáte s obtížnými instancemi.

Viz také

Reference

  1. ^ Garey, M. R.; Johnson, D. S. (Červenec 1978). "'Silné výsledky NP-úplnosti: motivace, příklady a důsledky “. Časopis Asociace pro výpočetní techniku. New York, NY: ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN  0004-5411. PAN  0478747.
  2. ^ Vazirani, Vijay V. (2003). Aproximační algoritmy. Berlín: Springer. 294–295. ISBN  3-540-65367-8. PAN  1851303.
  3. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (vyd.). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. Řada knih v matematických vědách. San Francisco, Kalifornie: W. H. Freeman and Co. pp.x + 338. ISBN  0-7167-1045-5. PAN  0519066.CS1 maint: ref = harv (odkaz)
  4. ^ H. Kellerer a U. Pferschy a D. Pisinger (2004). Problémy s batohem. Springer.CS1 maint: používá parametr autoři (odkaz)