NP
- För andra betydelser, se NP (olika betydelser).
NP betecknar mängden beslutsproblem som kan lösas på polynomiell tid av en icke-deterministisk Turingmaskin.
Bakgrund och informell definition
Inom komplexitetsteori, som kan sägas vara en del av datavetenskapen men också av matematiken, är man intresserad av att klassificera datavetenskapliga problem på ett formellt sätt, till exempel efter hur lång tid det tar att lösa dem eller hur mycket minne som krävs. En av de viktigaste klasserna av problem kallas NP. Man kan säga att NP består av de problem som visserligen kan ta lång tid att lösa, men där det i alla fall går effektivt att kontrollera lösningen om någon visar den för dig. I detta fall betyder "effektivt" att tidsåtgången för algoritmen beror som ett polynom av storleken på indata. Ett exempel på ett problem som ligger i NP är en variant av det som kallas handelsresandeproblemet (en. Travelling Salesman Problem eller TSP):
- En kringresande försäljare måste besöka ett antal städer och har bara viss begränsad tid på sig. För varje par av städer är det känt hur lång tid det tar att ta sig från den ena staden till den andra. Går det att hitta en resrutt som passerar genom alla städer på den angivna tiden?
Observera att man i praktiken behöver ange hur många städer det handlar om, avståndet mellan varje par av städer samt tidsbegränsningen. I datavetenskapen är man i allmänhet intresserad av att hitta generella metoder, som kan lösa vilken sådan given probleminstans som helst, det vill säga som tar antalet städer, avstånden och tidsbegränsningen som indata och svarar "ja" eller "nej". Det går att skriva ett datorprogram som i princip löser problemet för vilka indata som helst. Man kan till exempel låta det gå igenom alla möjliga resvägar, räkna ut tidsåtgången för var och en, och svara "ja" om en tillräckligt kort resrutt upptäcktes, och "nej" annars. Men ett sådant program kan bara lösa problemet inom rimlig tid när det handlar om mycket få städer -- antalet möjliga resvägar växer mycket snabbt då antalet städer växer. Man kan nu tänka sig att det är fel på just denna metod, och att det skulle kunna finnas snabbare algoritmer. Men ingen har hittat en sådan metod -- faktum är att för alla metoder som har föreslagits beror tiden av antalet städer på ett exponentiellt sätt.
TSP är ett exempel på ett problem som ligger i NP. Trots att det alltså inte finns någon känd polynomisk algoritm för att lösa problemet, går det att kontrollera en given lösning på polynomisk tid: Om någon säger vilken resväg den handelsresande ska ta, kan man enkelt verifiera att denna resväg tar högst den givna tiden, och sedan svara "ja" på frågan. Den givna resvägen kallas ett vittne för att svaret på frågan är ja. Om svaret däremot är "nej", går det (såvitt man vet) inte att hitta ett vittne för detta som kan kontrolleras på polynomisk tid. Definitionen av NP är alltså "asymmetrisk" i meningen att det bara behöver finnas vittnen för "ja"-svar. Problem där de enda möjliga svaren för probleminstanser är "ja" och "nej" kallas beslutsproblem (till skillnad från problem där svaret till exempel är en siffra), och NP består bara av beslutsproblem.
För att sammanfatta diskussionen, kan man säga att NP består av de beslutsproblem för vilka det finns ett polynom och en algoritm med följande egenskaper: för varje probleminstans av storlek n där svaret är "ja", finns det ett vittne, så att algoritmen givet probleminstansen och vittnet svarar "ja", och detta tar högst tid, men för probleminstanser där svaret är "nej" finns inget sådant vittne.
Observera att alla problem som kan lösas på polynomisk tid även utan vittne också passar definitionen (man kan då ta vad som helst som vittne), och alltså ligger i NP.
Den viktigaste anledningen till att man är intresserad av NP är teorin om NP-fullständiga problem. Kortfattat kan man säga att de NP-fullständiga beslutsproblemen är svårast av alla problem i NP, i bemärkelsen att varje algoritm för att lösa ett NP-fullständigt problem kan användas till att lösa alla andra problem i NP också, och det tar högst polynomiskt mycket längre tid.