P kontra NP – Definition, historia och betydelse som millennieproblem

Om du till exempel har ett problem och någon säger: "Svaret på ditt problem är mängden tal 1, 2, 3, 4, 5", kan en dator kanske snabbt räkna ut om svaret är rätt eller fel, men det kan ta mycket lång tid för datorn att faktiskt komma fram till "1, 2, 3, 4, 5" på egen hand. Ett annat exempel är att hitta primtal. Det är lätt att kontrollera om ett tal är primtal, men det är mycket svårt att hitta dessa tal överhuvudtaget. För vissa intressanta, praktiska frågor av det här slaget saknar vi ett sätt att snabbt hitta ett svar, men om vi får ett svar är det möjligt att snabbt kontrollera - det vill säga verifiera - svaret. På detta sätt kan NP-problem betraktas som gåtor: det kan vara svårt att komma på svaret på en gåta, men när man väl får höra svaret verkar det uppenbart. I denna jämförelse (analogi) är den grundläggande frågan: Är gåtor verkligen så svåra som vi tror att de är, eller missar vi något?

Eftersom den här typen av frågor om P kontra NP är så viktiga i praktiken vill många matematiker, forskare och datorprogrammerare bevisa det allmänna påståendet att varje problem som kontrolleras snabbt också kan lösas snabbt. Denna fråga är tillräckligt viktig för att Clay Mathematical Institute kommer att ge 1 000 000 dollar till den som lyckas ge ett bevis eller en giltig förklaring som motbevisar den.

Om vi gräver lite djupare ser vi att alla P-problem är NP-problem: det är lätt att kontrollera att en lösning är korrekt genom att lösa problemet och jämföra de två lösningarna. Människor vill dock veta om motsatsen: Finns det andra NP-problem än P-problem, eller är alla NP-problem bara P-problem? Om NP-problem verkligen inte är samma sak som P-problem (P ≠ NP) skulle det innebära att det inte finns några allmänna, snabba sätt att lösa dessa NP-problem, hur mycket vi än letar. Men om alla NP-problem är P-problem (P = NP) skulle det innebära att det finns nya, mycket snabba problemlösningsmetoder. Vi har bara inte hittat dem ännu.

Eftersom vetenskapsmän och matematiker ännu inte har hittat några allmänna och enkla metoder för att lösa NP-problem tror många att det finns andra NP-problem än P-problem (dvs. att P ≠ NP är sant). De flesta matematiker tror också att detta är sant, men för närvarande har ingen bevisat det genom rigorös matematisk analys. Om det kan bevisas att NP och P är samma sak (P = NP är sant) skulle det få en enorm inverkan på många aspekter av det dagliga livet. Därför är frågan om P kontra NP ett viktigt ämne som studeras flitigt.

Anta att någon vill bygga två torn genom att stapla stenar med olika massa. Man vill försäkra sig om att vart och ett av tornen har exakt samma massa. Det betyder att man måste lägga stenarna i två högar som har samma massa. Om man gissar en fördelning av stenarna som man tror kommer att fungera, skulle det vara lätt för en att kontrollera om man hade rätt. (För att kontrollera svaret kan man dela upp stenarna i två högar och sedan använda en våg för att se om de har samma massa). Eftersom det är lätt att kontrollera detta problem, som av datavetare kallas "Partition" - enklare än att lösa det direkt, som vi ska se - är det inte ett P-problem. ^[]

Hur svårt är det att lösa? Om man börjar med bara 100 stenar finns det 2^{100-1}-1 = 633,825,300,114,114,114,700,748,351,602,687, eller ungefär 6,3 x 10^{29} möjliga sätt (kombinationer) att dela upp dessa stenar i två högar. Om man kunde kontrollera en unik kombination av stenar varje dag skulle det ta 1,3 x 10^{22} eller 1 300 000 000 000 000 000 000 000 000 000 000 000 år av ansträngningar. Som jämförelse tror fysikerna att universum är ungefär 1,4 x 10^{10} år gammalt (450 000 000 000 000 000 000 000 000 000 eller ungefär 4,5 x 10^{17} sekunder, eller ungefär en triljondel så gammalt som den tid det skulle ta för vår ansträngning att stapla stenar. Det betyder att om man tar all den tid som har gått sedan universums början, skulle man behöva kontrollera mer än två biljoner (2 000 000 000 000 000 000) olika sätt att dela upp stenarna varje sekund, för att kontrollera alla olika sätt.

Om man programmerade en kraftfull dator för att testa alla dessa sätt att dela upp stenarna, skulle man kanske kunna kontrollera 1 000 000 000 {\displaystyle 1 000 000} kombinationer per sekund med nuvarande system. Detta innebär att man fortfarande skulle behöva 2 000 000 000 {\displaystyle 2 000 000} mycket kraftfulla datorer, som arbetat sedan universums början, för att testa alla sätt att dela upp stenarna.

Det kan dock vara möjligt att hitta en metod för att dela upp stenarna i två lika stora högar utan att kontrollera alla kombinationer. Frågan "Är P lika med NP?" är en förkortning för att fråga om en sådan metod kan existera.

Det finns många viktiga NP-problem som man inte vet hur man ska lösa på ett sätt som är snabbare än att testa alla möjliga svar. Här är några exempel:

• En resande försäljare vill besöka 100 städer med bil och börja och sluta sin resa hemma. Han har en begränsad mängd bensin, så han kan bara köra totalt 10 000 kilometer. Han vill veta om han kan besöka alla städer utan att bensinen tar slut.
• En skola har 100 olika klasser och en lärare måste välja en timme för varje klass' slutprov. För att förhindra fusk måste alla elever som deltar i en klass göra provet för den klassen vid samma tidpunkt. Om en elev läser mer än en klass måste alla dessa prov äga rum vid olika tidpunkter. Läraren vill veta om han kan schemalägga alla prov på samma dag så att alla elever kan göra provet för varje klass.
• En jordbrukare vill ta 100 vattenmeloner med olika massa till marknaden. Hon måste packa vattenmelonerna i lådor. Varje låda kan bara rymma 20 kilo utan att gå sönder. Jordbrukaren vill veta om 10 lådor räcker för att bära alla 100 vattenmeloner till marknaden. (Detta är trivialt, om inte mer än en vattenmelon väger mer än 2 kg kan 10 stycken placeras i varje låda, om inte mer än tio vattenmeloner väger mer än 2 kg kan en av varje vattenmelon placeras i varje låda, osv. för en snabb lösning; observation är nyckeln till en snabb lösning som denna eller problemet med taluppsättningar).
• Ett stort konstgalleri har många rum och varje vägg är täckt av många dyra målningar. Galleriets ägare vill köpa kameror för att bevaka målningarna om en tjuv skulle försöka stjäla någon av dem. Han vill veta om 100 kameror räcker för att se till att varje målning kan ses av minst en kamera.
• Cliqueproblemet: Rektorn på en skola har en lista över vilka elever som är vänner med varandra. Hon vill hitta en grupp på 10 % av eleverna som alla är vänner med varandra.

I exemplet ovan ser vi att med 100 {\displaystyle 100} stenar finns det 2 100 {\displaystyle 2^{100}} sätt att dela upp mängden stenar. Med n {\displaystyle n} stenar finns det 2 n {\displaystyle 2^{n}}} kombinationer. Funktionen f ( n ) = 2 n {\displaystyle f(n)=2^{n}}} är en exponentialfunktion. Den är viktig för NP eftersom den modellerar det värsta antalet beräkningar som behövs för att lösa ett problem och därmed den värsta tidsåtgången.

Och hittills har lösningarna för de svåra problemen krävt i storleksordningen 2 n {\displaystyle 2^{n}} beräkningar. För varje enskilt problem har man hittat sätt att minska antalet nödvändiga beräkningar. Man kan komma på ett sätt att göra bara 1 % av det värsta antalet beräkningar och det sparar mycket beräkningar, men det är fortfarande 0,01 × ( 2 n ) {\displaystyle 0,01\times (2^{n})} beräkningar. Och varje extra sten fördubblar fortfarande antalet beräkningar som behövs för att lösa problemet. Det finns insikter som kan ge metoder för att göra ännu färre beräkningar som ger variationer av modellen: t.ex. 2 n / n 3 {\displaystyle 2^{n}/n^{3}}} . Men exponentialfunktionen dominerar fortfarande när n {\displaystyle n} växer.

Tänk på problemet med schemaläggning av prov (beskrivet ovan). Men anta att det finns 15 000 studenter. Det finns ett datorprogram som tar fram schemat för alla 15000 studenter. Det körs på en timme och ger ut ett tentamensschema så att alla studenter kan göra sina tentor på en vecka. Det uppfyller många regler (inga tentor i rad, inte mer än två tentor under en 28-timmarsperiod, ...) för att begränsa stressen under tentamensveckan. Programmet körs i en timme vid halvtidsrasten och alla känner till sitt tentamensschema med gott om tid att förbereda sig.

Året därpå är det dock 10 fler elever. Om samma program körs på samma dator kommer den ena timmen att förvandlas till 2 10 {\displaystyle 2^{10}} timmar, eftersom varje ytterligare elev fördubblar beräkningarna. Det är 6 {\displaystyle 6} veckor! Om det fanns 20 fler elever, skulle

2 20 {\displaystyle 2^{20}} timmar = 1048576 {\displaystyle 1048576}timmar ~ 43691 {\displaystyle 43691} dagar ~ 113 {\displaystyle 113} år

För 15000 {\displaystyle 15000} elever tar det alltså en timme. För 15020 {\displaystyle 15020} studenter tar det 113 {\displaystyle 113} år.

Som du kan se växer exponentialfunktioner väldigt snabbt. De flesta matematiker tror att de svåraste NP-problemen kräver exponentiell tid för att lösas.

Matematiker kan visa att det finns vissa NP-problem som är NP-kompletta. Ett NP-komplett problem är minst lika svårt att lösa som alla andra NP-problem. Detta innebär att om någon hittar en metod för att snabbt lösa ett NP-komplett problem kan han eller hon använda samma metod för att snabbt lösa alla NP-problem. Alla de problem som anges ovan är NP-kompletta, så om försäljaren hittade ett sätt att snabbt planera sin resa kunde han berätta det för läraren, och hon kunde använda samma metod för att planera tentorna. Bonden skulle kunna använda samma metod för att bestämma hur många lådor hon behöver, och kvinnan skulle kunna använda samma metod för att hitta ett sätt att bygga sina torn.

Eftersom en metod som snabbt löser ett av dessa problem kan lösa dem alla är det många som vill hitta en sådan. Men eftersom det finns så många olika NP-kompletta problem och ingen hittills har hittat ett sätt att snabbt lösa ens ett av dem, anser de flesta experter att det inte är möjligt att snabbt lösa NP-kompletta problem.

Grundläggande egenskaper

Inom beräkningskomplexitetsteorin är komplexitetsklassen NP-complete (förkortat NP-C eller NPC) en klass av problem som har två egenskaper:

• Det ingår i mängden NP-problem (non-deterministic polynomial time): Varje given lösning på problemet kan verifieras snabbt (på polynomialtid).
• Det ingår också i mängden NP-hårda problem: De som är minst lika svåra som de svåraste problemen i NP. Problem som är NP-hårda behöver inte vara delar av NP; de kan till och med vara omöjliga att lösa.

Formell översikt

NP-complete är en delmängd av NP, mängden av alla beslutsproblem vars lösningar kan verifieras på polynomial tid. NP kan också definieras som mängden beslutsproblem som kan lösas på polynomial tid på en maskin. Ett problem p i NP ingår också i NPC om och endast om alla andra problem i NP kan omvandlas till p på polynomtid. NP-complete skulle användas som ett adjektiv: problem i klassen NP-complete var som NP+complete problem.

NP-kompletta problem studeras eftersom förmågan att snabbt verifiera lösningar på ett problem (NP) verkar korrelera med förmågan att snabbt lösa problem (P). Det har visat sig att alla problem i NP är snabbt lösta - de kallas P = NP: problemuppsättningen. Det enda problemet i NP-complete löses snabbt, snabbare än alla problem i NP som också löses snabbt, eftersom definitionen av ett NP-complete-problem anger att varje problem i NP snabbt måste kunna reduceras till varje problem i NP-complete (det reduceras på polynomialtid). [1]

Exempel

Det är känt att det booleska uppfyllbarhetsproblemet är NP-komplett. 1972 formulerade Richard Karp 21 problem som är kända för att vara NP-kompletta. Dessa är kända som Karps 21 NP-kompletta problem. De omfattar problem som t.ex. problemet med helgerprogrammering, som tillämpar linjär programmeringsteknik på helger, knapsackproblemet eller vertex cover-problemet.