NP klasse

I teorien om algoritmer er klasse NP (fra engelsk non-deterministic polynomial ) et sæt af løselighedsproblemer , hvis løsning kan kontrolleres på en Turing-maskine på en tid, der ikke overstiger værdien af et eller andet polynomium på størrelsen af inputtet data, med nogle yderligere oplysninger (den såkaldte beslutningsattest ) .

Tilsvarende inkluderer NP-klassen problemer, der kan løses i polynomiel tid på en ikke -deterministisk Turing-maskine .

Problemer, der har polynomial-tidsløsningsalgoritmer, kan løses ved hjælp af en computer meget hurtigere end ved direkte opregning, hvis tid er eksponentiel . Dette bestemmer den praktiske betydning af problemet med ligheden mellem klasserne P og NP .

Definitioner

Kompleksitetsklassen NP er defineret for et sæt sprog , det vil sige sæt af ord over et endeligt alfabet . Et sprog L siges at tilhøre klassen NP, hvis der eksisterer et to- steds prædikat fra klassen P (dvs. kan beregnes i polynomisk tid) og en konstant sådan, at for ethvert ord x er betingelsen " x hører til L " svarende til betingelsen "der er y af længde mindre end sådan, at den er sand " (hvor | x | er længden af ordet x ). Ordet y kaldes certifikatet for , at x hører til sproget L . Hvis vi således har et ord, der hører til sproget, og et andet vidneord af begrænset længde (som kan være svært at finde), så kan vi hurtigt verificere, at x virkelig hører til L . $\Sigma$ $R(x,\,y)$ $c>0$ $|x|^{c}$ $R(x,\,y)$

En ækvivalent definition kan opnås ved at bruge begrebet en ikke -deterministisk Turing-maskine (det vil sige en Turing-maskine, hvis program kan have forskellige linjer med samme venstre side). Hvis maskinen har mødt en "gaffel", det vil sige en tvetydighed i programmet, så er forskellige beregningsmuligheder yderligere mulige. Prædikatet , som repræsenterer en given ikke-deterministisk Turing-maskine, betragtes som lig med én, hvis der er mindst én beregningsmulighed, der returnerer 1, og nul, hvis alle optioner returnerer 0. Hvis længden af beregningen, der giver 1, ikke overstiger et eller andet polynomium i længden x , så kaldes prædikatet at høre til klassen NP. Hvis et sprog har et prædikat fra klassen NP, der genkender det, så siges sproget at tilhøre klassen NP. Denne definition svarer til den ovenfor anførte: Som vidne kan du tage numrene på de ønskede grene ved gaflerne i beregningen. Da længden af hele beregningsvejen for x , der tilhører sproget, ikke overstiger et polynomium i længden x , så vil vidnets længde også være begrænset af et polynomium i længden x . $R(x)$

Ethvert problem om medlemskabet af ordet x i sproget L , som ligger i klassen NP, kan løses i eksponentiel tid ved opregning af alle mulige certifikater med længde mindre end . For at løse det på en kvantecomputer kan du bruge GSA . I dette tilfælde kan det samlede antal af alle mulige certifikater, der skal sorteres fra, bestemmes af formlen for summen af medlemmer af en geometrisk progression med nævneren lig med antallet af tegn i alfabetet og 1. medlem lig med 1 : $|x|^{c}$ $|x|^{c}$ $|\Sigma |$ $\Sigma$

$N={\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}$

Derfor kræves der Q-bits for at slå det ønskede certifikat op ved hjælp af GSA-metoden . Certifikatet vil blive fundet inden for en tid, der ikke overstiger . $\left\lceil \log _{2}{\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}\right\rceil$ $O\venstre({\sqrt {\frac {1-|\Sigma |^{|x|^{c}}}{1-|\Sigma |}}}\right)$

Forholdet til andre klasser

Klassen af sprog, hvis komplementer tilhører NP, kaldes co-NP- klassen , selvom denne klasse ikke har vist sig at være adskilt fra NP-klassen. Skæringspunktet mellem klasserne NP og co-NP indeholder klassen P . Især klassen NP omfatter klassen P. Der vides dog intet om strengheden af denne inklusion.

Problemet med ligheden af klasserne P og NP er et af de centrale åbne problemer i teorien om algoritmer. Hvis de er ens, så kan ethvert problem fra NP-klassen løses hurtigt (i polynomisk tid). Imidlertid hælder det videnskabelige samfund til det negative svar på dette spørgsmål. [en]

NP-klassen er inkluderet i andre, bredere klasser, såsom PH-klassen . Der er også åbne spørgsmål om strengheden af dets optagelse i andre klasser.

Eksempler på problemer i klasse NP

Der kan anføres mange problemer, hvorom det i øjeblikket er uvist, om de tilhører P, men man ved, at de tilhører NP. Blandt dem:

Boolesk formeltilfredshedsproblem : at finde ud af en given boolesk formel , om der er et sæt variabler inkluderet i den, som gør det til 1. Et certifikat er et sådant sæt.
Klikeproblem : Givet en graf , skal du finde ud af, om den indeholder kliker (komplette undergrafer) af en given størrelse. Certifikat — antal hjørner, der danner en klike.
Bestemmelse af tilstedeværelsen af en Hamilton-cyklus i en graf . Et certifikat er en sekvens af hjørner, der danner en Hamilton-cyklus.
Ikke-optimeringsversionen af det rejsende sælgerproblem (er der en rute, der ikke er længere end en given værdi på k) er en udvidet og mere realistisk version af det tidligere problem. Et certifikat er sådan en rute.
Eksistensen af en heltalsløsning for et givet system af lineære uligheder. Certifikatet er løsningen.
Fraværet af et givet antal divisorer , således at . Certifikat - opdeling af et tal i primfaktorer sammen med deres primalitetscertifikater . $m$ $d$ $1<d\leq k$ $m$

Blandt alle problemer i NP-klassen kan man skelne mellem de "sværeste" - NP-komplette problemer . Hvis nogen af dem kan løses i polynomiel tid, så kan alle problemer i klasse NP også løses i polynomiel tid.

Se også

Noter

↑ William I. Gasarch. P=?NP-afstemningen. (neopr.) // SIGACT News. - 2002. - T. 33 , nr. 2 . - S. 34-47 . - doi : 10.1145/1052796.1052804 .

Litteratur

Thomas H. Kormen et al. 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 .
Søg opgaver. Klasserne P og NP. Intelligens. NP-Complete Problemer Arkiveret 13. juni 2011 på Wayback Machine
"Introduktion til strukturel kompleksitetsteori" . Foredragskursus.

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