NP komplett problem

NP-komplett problem - i teorin om algoritmer , ett problem med svaret "ja" eller "nej" från klassen NP , till vilket alla andra problem från denna klass kan reduceras i polynomtid (det vill säga med hjälp av operationer vars antal inte överstiger något polynom beroende på storleken på originaldata). Således bildar NP-kompletta problem på sätt och vis en delmängd av "typiska" problem i NP-klassen: om en "polynomiellt snabb" lösningsalgoritm hittas för några av dem, så kan alla andra problem från NP-klassen lösas lika "snabbt" ".

Formell definition

Ett alfabet är en ändlig uppsättning tecken (till exempel {} eller {}). Uppsättningen av alla möjliga ord (slutsträngar som består av tecknen i detta alfabet) över något alfabetbetecknas. Ett språk över ett alfabetär vilken delmängd som helst av mängden, dvs. ${0,1}$ ${a,b,c}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\subset \Sigma ^{*}$

Uppgiften att känna igen ett språk är att avgöra om ett givet ord tillhör språket . $L$ $L$

Låt och vara två språk över alfabetet . Ett språk sägs vara reducerbart (enligt Karp) till ett språk om det finns en funktion , , som är beräkningsbar i polynomtid och har följande egenskap: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\to \Sigma ^{*}$

$x\in L_{1}$ om och bara om . Karp-reducerbarhet betecknas som eller . $f(x)\i L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

Ett språk sägs vara NP-hårt om något språk i klassen NP är reducerbart till det. Ett språk sägs vara NP-komplett om det är NP-hårt och självt är i klassen NP. $L_{2}$

Informellt sett betyder det faktum att problemet reduceras till problemet att problemet "inte är svårare" än problemet (för om vi kan lösa , så kan vi lösa och ). Således inkluderar klassen av NP-hårda problem NP-kompletta problem och problem som är "svårare" än dem (det vill säga de problem till vilka NP-kompletta problem kan reduceras). NP-klassen inkluderar NP-kompletta problem och problem som är "enklare" än dem (det vill säga de problem som reduceras till NP-kompletta problem). $A$ $B$ $A$ $B$ $B$ $A$

Det följer av definitionen att om en algoritm hittas som löser något (vilket som helst) NP-komplett problem i polynomtid, så kommer alla NP-problem att vara i klassen P , det vill säga de kommer att lösas i polynomtid.

NP-komplett i stark mening

En uppgift kallas NP-komplett i stark mening om den har en deluppgift som:

är inte ett problem med numeriska parametrar (det vill säga att det maximala värdet för de mängder som påträffas i detta problem begränsas ovanifrån av ett polynom i längden på inmatningen)
är NP-komplett.

Klassen av sådana problem kallas NPCS . Om hypotesen P ≠ NP är sann, så finns det ingen pseudopolynomisk algoritm för NPCS-problemet .

Hypotes P ≠ NP

Frågan om sammanträffandet av klasserna P och NP har varit ett av de centrala öppna problemen i mer än trettio år . Det vetenskapliga samfundet tenderar att ge ett negativt svar på denna fråga [1] — i detta fall kommer det inte att vara möjligt att lösa NP-kompletta problem i polynomtid.

Exempel på NP-kompletta problem

Se även

Jämlikhet mellan klasserna P och NP

Anteckningar

↑ William I. Gasarch. P=?NP-undersökningen. (neopr.) // SIGACT News. - 2002. - T. 33 , nr 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .
↑ Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris är svårt, till och med ungefärligt . skriva ut.

Litteratur

Gary M., Johnson D. Datormaskiner och svåra problem Arkiverad 4 november 2019 på Wayback Machine . M.: Mir, 1982.
Thomas H. Kormen et al Kapitel 34. NP-Fullständighet // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M . : "Williams" , 2006. - 1296 sid. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion till automatteori, språk och beräkningar. - M . : "Williams" , 2002. - 528 sid. - ISBN 0-201-44124-1 .

Länkar

NP fullständighet
Beräkningskomplexiteten för spel och pussel Arkiverad 6 december 2006 på Wayback Machine
Ett kompendium av NP-optimeringsproblem. Redaktörer - Pierluigi Crescenzi, Viggo Kann Arkiverad 5 december 2006 på Wayback Machine

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA

NP-kompletta problem
Maximeringsproblem med stapling (packning)	Förpackning i behållare tvådimensionell packning linjär packning packning efter vikt förpackning efter värde Ryggsäcksproblemet
grafteori mängdteori	Vertex Cover Problem Klicka problem Problemet med en oberoende uppsättning (uppsättning) Ställtäckningsproblem Steiners problem Problemet med resande säljare Generaliserat resandeförsäljarproblem
Algoritmiska problem	Tillfredsställelseproblem för booleska formler (i konjunktiv normal form)
Logiska spel och pussel	Generaliserade taggar (spel i N 2 -1) kortaste lösningen problem Problem vars lösningar tillämpas i Tetris Generaliserat Sudoku problem Latinsk kvadrat fyllningsproblem Kakuros uppgift
Svårighetsklasser Operationsforskning Optimering Kombinatorisk optimering Tillämpad matematik Teori om algoritmer Dynamisk programmering 21 NP-komplett Karp-problem