NP komplet problem

NP-komplet problem - i teorien om algoritmer , et problem med svaret "ja" eller "nej" fra klassen NP , hvortil ethvert andet problem fra denne klasse kan reduceres i polynomisk tid (det vil sige ved hjælp af operationer, hvis antal ikke overstiger et eller andet polynomium afhængigt af størrelsen af de originale data). Således danner NP-komplette problemer på en måde en undergruppe af "typiske" problemer i NP-klassen: hvis der findes en "polynomisk hurtig" løsningsalgoritme for nogle af dem, så kan ethvert andet problem fra NP-klassen løses lige så "hurtigt" ".

Formel definition

Et alfabet er ethvert begrænset sæt af tegn (f.eks. {} eller {}). Sættet af alle mulige ord (endelige strenge sammensat af tegnene i dette alfabet) over et eller andet alfabeter betegnet. Et sprog over et alfabeter en hvilken som helst delmængde af sættet, dvs. ${0,1}$ ${a,b,c}$ $\Sigma$ $\Sigma ^{*}$ $L$ $\Sigma$ $\Sigma ^{*}$ $L\undersæt \Sigma ^{*}$

Opgaven med anerkendelse af et sprog er at afgøre, om et givet ord hører til sproget . $L$ $L$

Lad og vær to sprog over alfabetet . Et sprog siges at kunne reduceres (ifølge Karp) til et sprog, hvis der findes en funktion , , som kan beregnes i polynomisk tid og har følgende egenskab: $L_{1}$ $L_{2}$ $\Sigma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\to \Sigma ^{*}$

$x\in L_{1}$ hvis og kun hvis . Karp-reducerbarhed betegnes som eller . $f(x)\i L_{2}$ $L_{1}{\leq }_{p}L_{2}$ $L_{1}\varpropto L_{2}$

Et sprog siges at være NP-hårdt, hvis et sprog i klassen NP kan reduceres til det. Et sprog siges at være NP-komplet , hvis det er NP-hårdt og selv er i klassen NP. $L_{2}$

Uformelt set betyder det, at problemet er reduceret til problemet , at problemet "ikke er sværere" end problemet (for hvis vi kan løse , så kan vi løse og ). Klassen af NP-hårde problemer inkluderer således NP-komplette problemer og problemer, der er "sværere" end dem (det vil sige de problemer, som NP-komplette problemer kan reduceres til). NP-klassen inkluderer NP-komplette problemer og problemer, der er "lettere" end dem (det vil sige de problemer, der er reduceret til NP-komplette problemer). $EN$ $B$ $EN$ $B$ $B$ $EN$

Det følger af definitionen, at hvis der findes en algoritme, der løser et eller andet NP-fuldstændigt problem i polynomiel tid, så vil alle NP-problemer være i klassen P , det vil sige, at de bliver løst i polynomiel tid.

NP-komplet i stærk forstand

En opgave kaldes NP-komplet i stærk forstand , hvis den har en delopgave, der:

er ikke et problem med numeriske parametre (det vil sige, at den maksimale værdi af de mængder, der stødes på i denne opgave, er afgrænset ovenfra af et polynomium i længden af input)
er NP-komplet.

Klassen af sådanne problemer kaldes NPCS . Hvis hypotesen P ≠ NP er sand, er der ingen pseudopolynomial algoritme for NPCS-problemet .

Hypotese P ≠ NP

Spørgsmålet om sammenfaldet mellem klasserne P og NP har været et af de centrale åbne problemer i mere end tredive år . Det videnskabelige samfund har en tendens til at give et negativt svar på dette spørgsmål [1] - i dette tilfælde vil det ikke være muligt at løse NP-komplette problemer i polynomisk tid.

Eksempler på NP-komplette problemer

Se også

Ligestilling af klasserne P og NP

Noter

↑ William I. Gasarch. P=?NP-afstemningen. (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 er hård, endda til omtrentlig . Print.

Litteratur

Gary M., Johnson D. Computing machines and hard problems Arkiveret 4. november 2019 på Wayback Machine . M.: Mir, 1982.
Thomas H. Kormen et al. Kapitel 34. NP-fuldstændighed // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M . : "Williams" , 2006. - 1296 s. — ISBN 0-07-013151-1 .
John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .

Links

NP fuldstændighed
Beregningsmæssig kompleksitet af spil og puslespil Arkiveret 6. december 2006 på Wayback Machine
Et kompendium af NP-optimeringsproblemer. Redaktører - Pierluigi Crescenzi, Viggo Kann Arkiveret 5. december 2006 på Wayback Machine

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem