P och NP nästan utan datorsvammel

1928 ställde matematikern David Hilbert sitt Entscheidungs­problem. Frågan var: finns det en algoritm – alltså en ändlig, fast uppställning deterministiska beräkningssteg – som, givet ett formellt språk och ett valfritt matematiskt påstående på det språket, kan avgöra om påståendet är sant eller falskt?

Alonzo Church löste problemet 1936 – svaret är nej. 1937 kom Alan Turing självständigt fram till samma svar med en annorlunda metod, och den lösningen är mest känd. För att formalisera algoritmbegreppet introducerade han en teoretisk “maskin”, Turing­maskinen, som kan manipulera symboler på en remsa enligt en uppsättning regler.

Praktiska datorer är inspirerade av Turing­maskinen, och har stora likheter med den. Bland annat kan de beräkna samma saker, och de har också samma komplexitets­begränsningar: förhållandet mellan storleken på ett problem och den mängd tid och minne det tar att lösa följer samma mönster. (Principiellt gäller samma begränsningar också för människor under optimala förhållanden, det vill säga att de räknar rätt och i fast takt.)

Ett problem anses vara “hanterligt” om det kan lösas inom en tid som beskrivs av ett polynom i problems storlek, eller mindre (t.ex. n² mikrosekunder för att lösa ett beräkning med n poster). Dessa problem sägs tillhöra komplexitets­klassen P (”polynomial time”).

Turing­maskinen anses kunna beräkna alla funktioner som kan beräknas “effektivt”, vilket dock inte är bevisbart. Ett sätt att försöka motbevisa det är att luckra upp begränsningar i Turing­maskinens definition, där den mest uppenbara är att den är deterministisk, alltså alltid gör samma sak i varje givet tillstånd. Frågan är: om man låter den välja slump­mässigt mellan olika regler, kan den då lösa problem som en deterministisk Turing­maskin (DTM) inte kan? Med andra ord, kan den få fram ett korrekt svar på ändlig tid som en deterministisk aldrig kan nå, om man antar att den vid varje tillfälle väljer “rätt”?

(Gammalt datavetar­skämt – man kan sortera en lista i linjär tid enligt följande: välj en ordning slumpmässigt efter en kvant-slumpkälla. Om listan är oordnad, förstör universum. Om flervärlds­tolkningen stämmer har du rätt ordning i de världar som är kvar, annars finns det ingen kvar som kan klaga.)

Svaret på detta är nej; en ickedeterministisk Turing­maskin (NTM) är inte mer generell än en deterministisk, eftersom en NTM kan simuleras av en DTM. Däremot förefaller den vara snabbare: det finns problem som har polynomtids­lösningar på en NTM men ingen känd för DTM. Problem som kan lösas i polynomtid på en NTM tillhör komplexitets­klassen NP (”nondeterministic polynomial time”).

Alla problem i P tillhör också NP, men man vet inte om motsatsen gäller. Man skulle kunna bevisa att de är lika genom att lösa ett så kallat NP-fullständigt problem i polynomtid. Ett problem K är NP-fullständigt om man kan bevisa att alla problem i NP kan omformuleras till K.

Exempel på NP-fullständiga problem:

  • Handelsresandeproblemet: givet en uppsättning städer och vägar, hitta den kortaste rutten som besöker varje stad och slutar vid startpunkten. Uppenbara tillämpningar på logistik, men också mycket annat som programmering av industrirobotar.
  • Kappsäcksproblemet (med varianter): givet en uppsättning saker med olika volym och värde, välj ut den värdefullaste kombinationen som kan packas i en viss behållare. Viktigt för handelsresande, men också för schemaläggning och andra typer av planering.
  • Primtalsfaktorisering: givet ett stort tal x, hitta två primtal vars produkt är x. Grunden för de flesta kryptografiska system, eftersom det är väldigt lätt att bekräfta en korrekt lösning.
  • Diverse problem inom molkylärbiologi, till exempel multipel linjering/inpassning.

Den som löser ett NP-fullständigt problem har således en lysande karriär framför sig i speditionsbranschen. Dessutom väntar ett startkapital på en miljon dollar i form av Millenniepriset.

This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *