Om man sjekker en løsning i polynomisk tid, f.eks tre-farging av en graf, men det viser seg at løsningen ikke er entydig etter å sjekke alle mulige løsninger (eksponentiell kjøretid), putter man dette bare i NP da?

Og er det riktig å konkludere med at RSA-problemet er i NP? Å faktorisere har slik jeg forstår det polynomisk kjøretid, og for å sjekke om kvotienten videre er et primtall ble bevist i 2002 har polynomisk kjøretid (PRIMES). Det siste er vel kanskje overflødig da RSA mer eller mindre antar kun to distinkte faktorer.

Basert på et Piazza-spørsmål fra 2014

Definisjonen av NP inkluderer at man får et sertifikat for et ja-svar, og at man skal kunne verifisere dette sertifikatet i polynomisk tid, og altså dermed “overbevises” om at det er riktig å svare ja. For tre-farging vil en gyldig fargelegging av grafen være et eksempel på et slikt sertifikat. Det trenger ikke være det eneste mulige sertifikatet eller den eneste gyldige løsningen – så lenge det er nok til å bevise at «ja» er korrekt. Det samme gjelder faktorisering (som er det underliggende problemet i RSA-knekking): Om jeg gir deg en liste med primtallsfaktorer, så kan du i polynomisk tid verifisere at produktet er korrekt.

Faktorisering er ikke kjent å ha polynomisk kjøretid, forøvrig. Hvis det hadde vært det, så hadde man alt kunnet knekke RSA. Det er riktig at man kan sjekke om et tall er et primtall, men det tar eksponentielt lang tid å sjekke alle muligheter for den første faktoren. (Nok en gang dette med pseudopolynomisk, da…) Det kan forøvrig være interessant å merke seg at faktorisering ikke er kjent å være NP-komplett. Man har ingen polynomisk algoritme for det, og de fleste antar vel at en slik algoritme ikke finnes – men problemet antas altså å ligge utenfor både P og NPC, men inne i NP. Det betyr at om man løser et NPC-problem i polynomisk tid, slik at P = NP, så vil også faktorisering ligge i P (og i NPC), så det er riktig at løsning av et NPC-problem vil løse faktorisering, men man vet altså likevel ikke at/om faktorisering er i NPC.

Med «faktorisering» mente jeg da egentlig «divisjon», der man altså skal verifisere faktoren. Det var litt tvetydig formulert av meg.

Å, sånn ja! Dvs. spørsmålet ditt var at om jeg ga deg en faktor så kunne du sjekke at den og den andre faktoren (funnet ved divisjon) begge var primtall – og at hele denne operasjonen kunne gjøres i polynomisk tid? I så fall har du helt rett i det, ja.

Jeg er forøvrig i farten usikker på hva NP-beviset for primtallssjekking var før man fant ut at det var i P (som jo er en relativt ny og oppsiktsvekkende oppdagelse). Jeg tror kanskje jeg lette det opp til Python Algorithms, men jeg husker ikke i farten hva sertifikatet var. På den annen side er det lett å se at PRIMES (altså språket bestående av primtall) er i coNP, som er mengden av språk der komplementet er i NP. Dvs. «Er dette tallet ikke et primtall» er i NP. Det er jo lett å se (med din logikk) – sertifikatet er bare en faktor, f.eks. Dette blir da et coNP-sertifikat for PRIMES, men … jeg er usikker på hvordan et litt forståelig NP-sertifikat ser ut. (Siden man kan løse problemet i polynomisk tid, så vil jo tallet selv funke som et sertifikat, men det er ikke akkurat så “forståelig”, siden algoritmen er ganske knotete.)

OK, det er kanskje ikke så helt trivielt med primtallssertifikater, da: http://en.wikipedia.org/wiki/Primality_certificate