NP úplný problém

NP-úplný problém - v teorii algoritmů problém s odpovědí „ano“ nebo „ne“ z třídy NP , na který lze v polynomiálním čase redukovat jakýkoli jiný problém z této třídy (tj. pomocí operací, jejichž počet nepřesahuje nějaký polynom v závislosti na velikosti původních dat). NP-úplné problémy tedy tvoří v jistém smyslu podmnožinu „typických“ problémů ve třídě NP: pokud je pro některé z nich nalezen „polynomiálně rychlý“ algoritmus řešení, lze vyřešit jakýkoli jiný problém ze třídy NP. stejně „rychle““.

Formální definice

Abeceda je jakákoli konečná množina znaků (například {} nebo {}). Množina všech možných slov (koncové řetězce složené ze znaků této abecedy) nad nějakou abecedouje označena. Jazyk nad abecedouje jakákoli podmnožina množiny, tj. ${0,1}$ ${a,b,c}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\subset \Sigma ^{*}$

Úkolem rozpoznávání jazyka je určit, zda dané slovo patří do jazyka . $L$ $L$

Dovolit a být dva jazyky přes abecedu . Říká se, že jazyk je redukovatelný (podle Karpa) na jazyk , pokud existuje funkce , , která je vyčíslitelná v polynomiálním čase a má následující vlastnost: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\to \Sigma ^{*}$

$x\in L_{1}$ pokud a jen tehdy . Karp redukovatelnost se označuje jako nebo . $f(x)\in L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

O jazyce se říká , že je NP-tvrdý , pokud je na něj jakýkoli jazyk ve třídě NP redukovatelný. O jazyce se říká , že je NP-úplný , pokud je NP-tvrdý a je sám ve třídě NP. $L_{2}$

Neformálně řečeno, skutečnost, že se problém redukuje na problém , znamená, že problém „není těžší“ než problém (protože když dokážeme vyřešit , můžeme vyřešit a ). Třída NP-těžkých problémů tedy zahrnuje NP-úplné problémy a problémy, které jsou „těžší“ než ony (tj. ty problémy, na které lze NP-úplné problémy redukovat). Třída NP zahrnuje NP-úplné problémy a problémy, které jsou „snazší“ než ony (tedy ty problémy, které jsou redukovány na NP-úplné problémy). $A$ $B$ $A$ $B$ $B$ $A$

Z definice vyplývá, že pokud se najde algoritmus, který řeší nějaký (jakýkoli) NP-úplný problém v polynomiálním čase, pak všechny NP-problémy budou ve třídě P , to znamená, že budou vyřešeny v polynomiálním čase.

NP-úplný v silném smyslu

Úkol se nazývá NP-úplný v silném smyslu , pokud má dílčí úkol, který:

není problém s numerickými parametry (to znamená, že maximální hodnota veličin, se kterými se v tomto problému setkáváme, je shora ohraničena polynomem v délce vstupu)
je NP-úplný.

Třída takových problémů se nazývá NPCS . Pokud je hypotéza P ≠ NP pravdivá, pak pro problém NPCS neexistuje žádný pseudopolynomiální algoritmus .

Hypotéza P ≠ NP

Otázka koincidence tříd P a NP je jedním z ústředních otevřených problémů již více než třicet let . Vědecká komunita má tendenci dávat na tuto otázku zápornou odpověď [1] — v tomto případě nebude možné řešit NP-úplné problémy v polynomiálním čase.

Příklady NP-úplných problémů

Viz také

Rovnost tříd P a NP

Poznámky

↑ Vilém I. Gasarch. Průzkum P=?NP. (neopr.) // Zprávy SIGACT. - 2002. - T. 33 , č. 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris je těžký, dokonce i přibližný . tisk.

Literatura

Gary M., Johnson D. Výpočetní stroje a těžké problémy Archivováno 4. listopadu 2019 na Wayback Machine . M.: Mir, 1982.
Thomas H. Kormen a kol. , Kapitola 34. NP-úplnost // Algoritmy: Konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Odkazy

Úplnost NP
Computational Complexity of Games and Puzzles Archived 6. prosince 2006 na Wayback Machine
Přehled úloh optimalizace NP. Editoři - Pierluigi Crescenzi, Viggo Kann Archivováno 5. prosince 2006 na Wayback Machine

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém