Karps 21 NP - kompletní problémy - Karps 21 NP-complete problems - Wikipedia

v teorie výpočetní složitosti, Karpových 21 NP-úplných problémů jsou souborem výpočetní problémy což jsou NP-kompletní. Ve svém příspěvku z roku 1972 „Reducibility Among Combinatorial Problems“ ^[1] Richard Karp použitý Stephen Cook věta z roku 1971, že booleovský problém uspokojivosti je NP-kompletní^[2] (nazývané také Cook-Levinova věta ) ukázat, že existuje polynomiální čas mnoho-jedna redukce od problému s booleovskou uspokojivostí ke každému z 21 kombinační a graf teoretický výpočetní problémy, což ukazuje, že jsou všechny NP úplné. Jednalo se o jednu z prvních ukázek mnoha přirozených výpočetních problémů, které se vyskytly počítačová věda jsou výpočetně neřešitelný, a to vyvolalo zájem o studium NP-úplnosti a Problém P versus NP.

Problémy

Níže je uvedeno 21 Karpových problémů, mnoho s jejich původními názvy. Vnoření označuje směr použitých redukcí. Například, Batoh se ukázalo být NP-kompletní redukcí Přesné krytí na Batoh.

• Splnitelnost: problém booleovské uspokojivosti vzorců ve Windows konjunktivní normální forma (často označované jako SAT)
  • Programování celého čísla 0–1 (Varianta, ve které musí být splněna pouze omezení, bez optimalizace)
  • Klika (viz také problém nezávislé množiny )
    • Nastavit balení
    • Vrcholový kryt
      • Sada krytiny
      • Sada uzlů zpětné vazby
      • Sada zpětné vazby
      • Směrovaný Hamiltonův okruh (Karpovo jméno, nyní obvykle volané Směrovaný hamiltonovský cyklus)
        • Neusměrněný Hamiltonův obvod (Karpovo jméno, nyní obvykle volané Neusměrněný hamiltonovský cyklus)
  • Splnitelnost s maximálně 3 literály na klauzuli (ekvivalent 3-SAT)
    • Chromatické číslo (nazývané také Problém s barvením grafu )
      • Clique kryt
      • Přesné krytí
        • Bít set
        • Steinerův strom
        • 3-dimenzionální shoda
        • Batoh (Karpova definice batohu je blíže Součet podmnožiny )
          • Sekvenování úloh
          • Rozdělit
            • Maximální řez

Postupem času bylo zjištěno, že mnoho problémů lze efektivně vyřešit, pokud jsou omezeny na zvláštní případy, nebo je lze vyřešit v jakémkoli pevném procentu optimálního výsledku. Nicméně, David Zuckerman v roce 1996 ukázal, že každý z těchto 21 problémů má omezenou optimalizační verzi, kterou není možné aproximovat v rámci žádného konstantního faktoru, pokud P = NP, a to tím, že ukazuje, že Karpov přístup k redukci zobecňuje konkrétní typ redukce aproximace.^[3] Všimněte si však, že se mohou lišit od standardních optimalizačních verzí problémů, které mohou mít aproximační algoritmy (jako v případě maximálního řezu).

Viz také

• Seznam NP-úplných problémů

Poznámky

Reference

• Stephen Cook (1971). „Složitost postupů prokazování věty“. Proc. 3. ročník ACM symposia o teorii práce na počítači (STOC). 151–158. doi:10.1145/800157.805047.CS1 maint: ref = harv (odkaz)
• Richard M. Karp (1972). „Reducibilita mezi kombinatorickými problémy“ (PDF). R. R. Miller; J. W. Thatcher; J.D.Bohlinger (eds.). Složitost počítačových výpočtů. New York: Plenum. str. 85–103. doi:10.1007/978-1-4684-2001-2_9. ISBN  978-1-4684-2003-6.CS1 maint: ref = harv (odkaz)
• Zuckerman, David (1996). „O nepřijatelných verzích NP-úplných problémů“. SIAM Journal on Computing. 25 (6): 1293–1304. doi:10.1137 / S0097539794266407.CS1 maint: ref = harv (odkaz) [1]