I komplexitetsteorin studerar vi inte bara om ett problem går att lösa, utan hur svårt det är att lösa. När vi säger att ett problem är “effektivt lösbart” menar vi vanligen att det finns en algoritm vars körtid växer polynomiellt med indata-storleken. Klassen av alla sådana beslutsproblem kallas P (för polynomial time).
Man insåg snart att denna definition lämnar en lucka. För många problem verkar det hopplöst svårt att hitta en lösning, men om någon ger oss en föreslagen lösning, kan vi kontrollera dess giltighet snabbt. Denna observation ledde till klassen NP, definierad som mängden språk A för vilka det finns ett språk B ∈ P och ett polynom p så att
x ∈ A ⇔ ∃y, |y| ≤ p(|x|) : (x, y) ∈ B.
Alltså: det finns ett vittne (en lösning, ett bevis), y, av polynomiell längd som övertygar en polynomiskt effektiv verifierare om att x bör accepteras.
Klasskillnaden mellan P och NP handlar inte om datorns fysik, utan om kognitiv asymmetri: skillnaden mellan att skapa en lösning och att känna igen den när den visas. Att lösa Sudoku kan ta tid, men att kontrollera ett färdigt förslag går snabbt. Att hitta en Hamiltoncykel i en graf är svårt, men att verifiera en given cykel är trivialt.
Det centrala olösta problemet är förstås frågan
P = NP ?
Om svaret vore ja, skulle varje problem vars lösning kan verifieras effektivt också kunna lösas effektivt. Det skulle i grunden förändra vår uppfattning om kreativitet, bevis, och beräkning: varje gåta med ett snabbt igenkännligt svar skulle kunna besvaras lika snabbt som den kunde verifieras. De flesta forskare tror dock att P ≠ NP: att det finns en verklig klyfta mellan att känna igen sanningen och att finna den.
Formeln i NP-definitionen innehåller en existenskvantifikator: ∃y. Man kan se det som att ett problem i NP frågar: “Finns det ett vittne som övertygar verifieraren?” Men varför stanna där? Vad händer om vi lägger till ytterligare kvantifikatorer?
Tänk på ett problem där inte bara ett vittne ska hittas, utan där varje möjlig invändning måste kunna bemötas. Vi skulle då vilja uttrycka något som
x ∈ A ⇔ ∃y₁ ∀y₂ : (x, y₁, y₂) ∈ B, där B ∈ P.
Här växlar vi mellan existens och universalitet, mellan “någon kan vinna” och “ingen kan motbevisa”. Detta leder oss till begreppet alternation, en generalisering av icke-determinism. I stället för att bara gissa en lösning (∃), tillåter vi ett växelspel mellan två aktörer: en existentiell spelare som försöker bevisa att instansen accepteras, och en universell som försöker motbevisa det.
Genom att tillåta fler växlingar av kvantifikatorer får vi en hel polynomiell hierarki av klasser:
Σ₁P = NP, Π₁P = coNP,
Σ₂P = { A | ∃y₁ ∀y₂ : (x, y₁, y₂) ∈ B, B ∈ P },
Π₂P = { A | ∀y₁ ∃y₂ : (x, y₁, y₂) ∈ B, B ∈ P }, osv.
Denna hierarki kan ses som en oändlig stege av växlande bevisbörda: varje nivå tillåter ytterligare ett lager av resonemang mellan bevis och motbevis, attacker och försvar.
Om vi någon gång skulle upptäcka att P = NP, skulle hela hierarkin kollapsa till basnivån: alla dessa komplexa former av interaktion skulle kunna lösas lika lätt som vanliga P-problem. Men varje försök att bevisa eller motbevisa detta har hittills misslyckats.
Ur ett logiskt perspektiv är NP exakt mängden av språk som kan uttryckas av formler i existentiell andra ordningens logik (Fagin, 1974):
∃R₁, …, Rₖ : φ(x, R₁, …, Rₖ),
där φ är en första ordningens formel som beskriver de polynomiella verifieringsstegen. Att gå från P till NP innebär alltså att gå från deterministisk beräkning till existentiell logik. Och att gå vidare upp i den polynomiella hierarkin är att växla mellan existentiella och universella kvantifikatorer, en slags beräkningsmässig dialektik.
Ur filosofisk synvinkel kan vi tolka dessa klasser som nivåer av kunskap. P-problem är sådant vi kan beräkna direkt. NP-problem är sådant vi kan känna igen när vi ser det. Π₂-problem är sådant vi kan känna igen trots alla invändningar. Och så vidare.
Beräkning blir då inte bara en fråga om tid och resurser, utan om hur många lager av resonemang som krävs för att övertyga en rationell agent. Varje kvantifikator motsvarar ett skifte mellan bevis och tvivel, mellan hopp och motstånd.
Från P till NP, och vidare upp genom den polynomiella hierarkin, ser vi en gradvis förfining av vad “att lösa” betyder. NP fångar det första steget bortom det mekaniska: den beräkning som kräver en gissning, en idé, ett vittne. Nästa steg, Σ₂ och Π₂, visar att vissa problem kräver en hel dialog mellan bevis och motbevis.
Kanske är det därför frågan om P = NP känns så grundläggande: den handlar inte bara om algoritmer, utan om själva gränsen mellan beräkning och förståelse. Om det visar sig att P ≠ NP, då är det en påminnelse om att vissa sanningar är lätta att känna igen men svåra att finna. Och om de någon gång visar sig vara lika, då betyder det att varje insikt som kan verifieras, också kan upptäckas, bara snabbare än vi någonsin trodde möjligt.