NP (komplexitet)

Olöst problem inom datavetenskap :

${\mathsf {P\ {\overset {?}{=}}\ NP}}$

(fler olösta problem inom datavetenskap)

Euler-diagram för P , NP, NP-komplett och NP-hård uppsättning problem. Under antagandet att P ≠ NP, fastställdes förekomsten av problem inom NP men utanför både P och NP-komplett av Ladner .

I beräkningskomplexitetsteori är NP ( nondeterministic polynomial time ) en komplexitetsklass som används för att klassificera beslutsproblem . NP är uppsättningen beslutsproblem för vilka probleminstanserna , där svaret är "ja", har bevis som kan verifieras i polynomtid av en deterministisk Turing-maskin , eller alternativt den uppsättning problem som kan lösas i polynomtid med en icke-deterministisk Turing maskin .

En ekvivalent definition av NP är uppsättningen beslutsproblem som kan lösas i polynomtid av en icke-deterministisk Turing-maskin . Denna definition är grunden för förkortningen NP; " icke-deterministisk , polynomisk tid". Dessa två definitioner är likvärdiga eftersom algoritmen baserad på Turing-maskinen består av två faser, varav den första består av en gissning om lösningen, som genereras på ett icke-deterministiskt sätt, medan den andra fasen består av en deterministisk algoritm som verifierar om gissningen är en lösning på problemet.

Det är lätt att se att komplexitetsklassen P (alla problem lösbara, deterministiskt, i polynomtid) finns i NP (problem där lösningar kan verifieras i polynomtid), för om ett problem är lösbart i polynomtid, då är en lösning är också verifierbar i polynomtid genom att helt enkelt lösa problemet. Men NP innehåller många fler problem, varav de svåraste kallas NP-kompletta problem. En algoritm som löser ett sådant problem i polynomtid kan också lösa vilket annat NP-problem som helst i polynomtid. Det viktigaste P kontra NP ("P = NP?")-problemet frågar sig om det finns polynomtidsalgoritmer för att lösa NP-kompletta, och därmed, alla NP-problem. Det är en allmän uppfattning att så inte är fallet.

Komplexitetsklassen NP är relaterad till komplexitetsklassen co-NP , för vilken svaret "nej" kan verifieras i polynomtid. Huruvida NP = co-NP är en annan framstående fråga inom komplexitetsteorin.

Formell definition

Komplexitetsklassen NP kan definieras i termer av NTIME enligt följande:

${\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n ^{k}),$

där ${\mathsf {NTIME}}(n^{k})$ är uppsättningen beslutsproblem som kan lösas av en icke-deterministisk Turingmaskin i ${ \displaystyle O(n^{k})}$ tid.

Alternativt kan NP definieras med deterministiska Turing-maskiner som verifierare. Ett språk L är i NP om och endast om det finns polynom p och q , och en deterministisk Turingmaskin M , så att

• För alla x och y kör maskinen M i tiden p (| x |) på ingången $(x,y)$ .
• För alla x i L finns det en sträng y med längden q (| x |) så att $M(x,y)=1$ .
• För alla x inte i L och alla strängar y med längden q (| x |), $M(x,y)=0$ .

Bakgrund

Många datavetenskapliga problem finns i NP, som beslutsversioner av många sök- och optimeringsproblem.

Verifier-baserad definition

För att förklara den verifierbaserade definitionen av NP, överväg delmängdssummaproblemet : Antag att vi får några heltal , {−7, −3, −2, 5, 8}, och vi vill veta om några av dessa heltal summerar till noll. Här är svaret "ja", eftersom heltalen {−3, −2, 5} motsvarar summan (−3) + (−2) + 5 = 0.

För att svara på om några av heltalen adderas till noll kan vi skapa en algoritm som får alla möjliga delmängder. När antalet heltal som vi matar in i algoritmen blir större, växer både antalet delmängder och beräkningstiden exponentiellt.

Men lägg märke till att om vi får en viss delmängd kan vi effektivt verifiera om delmängdens summa är noll, genom att summera delmängdens heltal. Om summan är noll är den delmängden ett bevis eller ett vittne för svaret är "ja". En algoritm som verifierar om en given delmängd har summan noll är en verifierare . Helt klart kan summering av en delmängds heltal göras i polynomtid, och delmängdens summaproblem är därför i NP.

Ovanstående exempel kan generaliseras för alla beslutsproblem. Givet varje fall I av problem $\Pi$ och vittne W, om det finns en verifierare V så att givet det ordnade paret (I, W) som indata, returnerar V "ja" i polynomtid om vittnet bevisar att svaret är "ja" eller "nej" i polynomtid annars, då är $\Pi$ i NP.

"Nej"-svarsversionen av detta problem anges som: "med en ändlig uppsättning heltal, har varje icke-tom delmängd en summa som inte är noll?". Den verifierbaserade definitionen av NP inte en effektiv verifierare för "nej"-svaren. Klassen av problem med sådana verifierare för "nej"-svaren kallas co-NP. Faktum är att det är en öppen fråga om alla problem i NP också har verifierare för "nej"-svaren och därmed finns i co-NP.

I viss litteratur kallas verifieraren "certifierare" och vittnet för " certifikat ".

Maskindefinition

Likvärdig med den verifierbaserade definitionen är följande karakterisering: NP är klassen av beslutsproblem som kan lösas av en icke-deterministisk Turing-maskin som körs i polynomtid . Det vill säga, ett beslutsproblem $\Pi$ är i NP närhelst $\Pi$ känns igen av någon polynom-tids icke-deterministisk Turingmaskin $M$ med ett existentiellt acceptansvillkor , vilket betyder att $w\in \Pi$ om och endast om någon beräkningsväg för $M(w)$ leder till ett accepterande tillstånd. Denna definition är ekvivalent med den verifierbaserade definitionen eftersom en icke-deterministisk Turing-maskin skulle kunna lösa ett NP-problem i polynomtid genom att icke-deterministiskt välja ett certifikat och köra verifieraren på certifikatet. På liknande sätt, om en sådan maskin existerar, kan en polynomtidsverifierare naturligtvis konstrueras från den.

I detta ljus kan vi definiera co-NP dubbelt som klassen av beslutsproblem som kan kännas igen av polynom-tids-icke-deterministiska Turing-maskiner med ett existentiellt avslagstillstånd. Eftersom ett existentiellt avslagsvillkor är exakt samma sak som ett universellt acceptansvillkor , kan vi förstå NP vs. co-NP- frågan som att fråga om de existentiella och universella acceptansvillkoren har samma uttryckskraft för klassen av polynom-tids-icke-deterministisk Turing maskiner.

Egenskaper

NP är stängd under union , korsning , sammanlänkning , Kleene-stjärna och reversering . Det är inte känt om NP är stängt under komplement (denna fråga är den så kallade "NP kontra co-NP"-frågan).

Varför vissa NP-problem är svåra att lösa

På grund av de många viktiga problemen i denna klass har det gjorts omfattande ansträngningar för att hitta polynomtidsalgoritmer för problem i NP. Det finns dock fortfarande ett stort antal problem i NP som trotsar sådana försök, som verkar kräva superpolynomtid . Huruvida dessa problem inte kan avgöras i polynomtid är en av de största öppna frågorna inom datavetenskap (se P versus NP ("P = NP") problem för en djupgående diskussion).

En viktig föreställning i detta sammanhang är uppsättningen av NP-kompletta beslutsproblem, som är en delmängd av NP och kan informellt beskrivas som de "svåraste" problemen i NP. Om det finns en polynomtidsalgoritm för ens en av dem, så finns det en polynomtidsalgoritm för alla problem i NP. På grund av detta, och eftersom dedikerad forskning har misslyckats med att hitta en polynomalgoritm för något NP-komplett problem, när ett problem har bevisats vara NP-komplett, anses detta allmänt vara ett tecken på att en polynomalgoritm för detta problem är osannolik. att existera.

Men i praktisk användning, istället för att lägga beräkningsresurser på att leta efter en optimal lösning, kan en tillräckligt bra (men potentiellt suboptimal) lösning ofta hittas i polynomtid. Dessutom är de verkliga tillämpningarna av vissa problem lättare än deras teoretiska motsvarigheter.

Likvärdighet mellan definitioner

De två definitionerna av NP som klassen av problem som kan lösas av en icke-deterministisk Turingmaskin (TM) i polynomtid och klassen av problem som kan verifieras av en deterministisk Turingmaskin i polynomtid är ekvivalenta. Beviset beskrivs av många läroböcker, till exempel Sipsers introduktion till teorin om beräkning , avsnitt 7.3.

För att visa detta, anta först att vi har en deterministisk verifierare. En icke-deterministisk maskin kan helt enkelt odeterministiskt köra verifieraren på alla möjliga bevissträngar (detta kräver bara polynomiellt många steg eftersom den odeterministiskt kan välja nästa tecken i bevissträngen i varje steg, och längden på bevissträngen måste vara polynomiellt avgränsad ). Om något bevis är giltigt, kommer någon väg att acceptera; om inget bevis är giltigt finns inte strängen på språket och den kommer att avvisas.

Omvänt, anta att vi har en icke-deterministisk TM som kallas A som accepterar ett givet språk L. Vid vart och ett av dess polynomiellt många steg förgrenar sig maskinens beräkningsträd i högst ett ändligt antal riktningar. Det måste finnas minst en accepterande sökväg, och strängen som beskriver denna väg är beviset som tillhandahålls verifieraren. Verifieraren kan sedan deterministiskt simulera A, följa endast den accepterande vägen och verifiera att den accepterar i slutet. Om A avvisar inmatningen, finns det ingen acceptansväg, och verifieraren kommer alltid att avvisa.

Förhållande till andra klasser

En representation av förhållandet mellan komplexitetsklasser

Inklusioner av komplexitetsklasser inklusive P , NP , co-NP , BPP , P/poly , PH och PSPACE

NP innehåller alla problem i P , eftersom man kan verifiera vilken instans som helst av problemet genom att helt enkelt ignorera beviset och lösa det. NP finns i PSPACE — för att visa detta räcker det med att konstruera en PSPACE-maskin som loopar över alla bevissträngar och matar var och en till en polynom-tidsverifierare. Eftersom en polynom-tidsmaskin bara kan läsa polynomiellt många bitar, kan den inte använda mer än polynomutrymme, och den kan inte heller läsa en bevissträng som upptar mer än polynomutrymme (så vi behöver inte överväga bevis längre än så här). NP finns också i EXPTIME , eftersom samma algoritm fungerar i exponentiell tid.

co-NP innehåller de problem som har ett enkelt bevis för inga instanser, ibland kallade motexempel. Primalitetstestning ligger till exempel trivialt i co-NP, eftersom man kan motbevisa primaaliteten hos ett heltal genom att bara ange en icke-trivial faktor. NP och co-NP bildar tillsammans den första nivån i polynomhierarkin , endast högre än P.

NP definieras endast med deterministiska maskiner. Om vi ​​tillåter verifieraren att vara probabilistisk (detta är dock inte nödvändigtvis en BPP-maskin), får vi klassen MA lösbar med hjälp av ett Arthur–Merlin-protokoll utan kommunikation från Arthur till Merlin.

Relationen mellan BPP och NP är okänd: det är inte känt om BPP är en delmängd av NP , NP är en delmängd av BPP eller ingetdera. Om NP finns i BPP , vilket anses osannolikt eftersom det skulle innebära praktiska lösningar för NP-kompletta problem, då NP = RP och PH ⊆ BPP .

NP är en klass av beslutsproblem ; den analoga klassen av funktionsproblem är FNP .

De enda kända strikta inneslutningarna kommer från tidshierarkisatsen och rymdhierarkisatsen , och de är respektive ${\mathsf {NP\subsetneq NEXPTIME}}$ och ${\mathsf {NP\subsetneq EXPSPACE}}$ .

Andra karaktäriseringar

När det gäller beskrivande komplexitetsteori motsvarar NP exakt den uppsättning språk som kan definieras av existentiell andra ordningens logik ( Fagins teorem) .

NP kan ses som en mycket enkel typ av interaktivt bevissystem , där provaren kommer med beviscertifikatet och verifieraren är en deterministisk polynom-tidsmaskin som kontrollerar det. Den är komplett eftersom den rätta bevissträngen kommer att få den att acceptera om det finns en, och den är bra eftersom verifieraren inte kan acceptera om det inte finns någon acceptabel bevissträng.

Ett viktigt resultat av komplexitetsteorin är att NP kan karakteriseras som de problem som kan lösas av probabilistiskt kontrollerbara bevis där verifieraren använder O(log n ) slumpmässiga bitar och undersöker endast ett konstant antal bitar av bevissträngen (klassen PCP (log n) , 1)). Mer informellt innebär detta att NP-verifieraren som beskrivs ovan kan ersättas med en som bara "spot-checkar" några få ställen i bevissträngen, och genom att använda ett begränsat antal myntvändningar kan det med stor sannolikhet fastställa det korrekta svaret. Detta gör att flera resultat om hårdheten hos approximationsalgoritmer kan bevisas.

Exempel

P

Alla problem i P , betecknade ${\mathsf {P\subseteq NP}}$ . Med ett certifikat för ett problem i P kan vi ignorera certifikatet och bara lösa problemet i polynomtid.

Heltalsfaktorisering

Beslutsproblemversionen av heltalsfaktoriseringsproblemet : givet heltal n och k , finns det en faktor f med 1 < f < k och f som delar n ?

NP-kompletta problem

Huvudartikel: Lista över NP-kompletta problem

Varje NP-komplett problem finns i NP.

Boolesk tillfredsställelse

Det booleska satisfiability-problemet ( SAT ), där vi vill veta om en viss formel i propositionslogik med booleska variabler är sann för något värde av variablerna.

Resande säljare

Beslutsversionen av resandeförsäljarproblemet finns i NP. Givet en inmatningsmatris av avstånd mellan n städer, är problemet att avgöra om det finns en rutt som besöker alla städer med totalt avstånd mindre än k .

Ett bevis kan helt enkelt vara en lista över städerna. Då kan verifiering helt klart göras i polynomtid. Den lägger helt enkelt till matrisposterna som motsvarar vägarna mellan städerna.

En icke-deterministisk Turing-maskin kan hitta en sådan väg som följer:

• Vid varje stad den besöker kommer den att "gissa" nästa stad att besöka, tills den har besökt varje vertex. Om den fastnar stannar den direkt.
• I slutet verifierar den att rutten den har tagit har kostat mindre än k i O ( n ) tid.

Man kan tänka på varje gissning som att " gaffel " en ny kopia av Turing-maskinen för att följa var och en av de möjliga vägarna framåt, och om åtminstone en maskin hittar en rutt med avstånd mindre än k , accepterar den inmatningen. (På samma sätt kan detta ses som en enda Turing-maskin som alltid gissar rätt)

En binär sökning på intervallet av möjliga avstånd kan konvertera beslutsversionen av Traveling Salesman till optimeringsversionen, genom att anropa beslutsversionen upprepade gånger (ett polynomantal gånger).

Subgraf isomorfism

Subgrafisomorfismproblemet att avgöra om graf G innehåller en subgraf som är isomorf mot graf H .

Se även

• Turingmaskin – Beräkningsmodell som definierar en abstrakt maskin

Vidare läsning

•   Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest och Clifford Stein . Introduktion till algoritmer, andra upplagan. MIT Press och McGraw-Hill, 2001. ISBN 0-262-03293-7 . Avsnitt 34.2: Polynom-tidsverifiering, s. 979–983.
•   Michael Sipser (1997). Introduktion till teorin om beräkning . PWS Publishing. ISBN 0-534-94728-X . Avsnitt 7.3–7.5 (Klassen NP, NP-fullständighet, Ytterligare NP-fullständiga problem), s. 241–271.
• David Harel , Yishai Feldman. Algoritmik: The Spirit of Computing, Addison-Wesley, Reading, MA, 3:e upplagan, 2004.

externa länkar

• Komplexitet Zoo : NP
• American Scientist primer om traditionell och ny komplexitetsteorisk forskning: "Accidental Algorithms"