Hva er egentlig verifikasjon?
Intuitivt virker det jo enkelt å si at en verifikasjonsalgoritme «sjekker svaret», og at vi kan verifisere løsningene til problemer i NP. Men om man ser litt mer formelt på det, ser det plutselig litt snodigere ut. Hvordan fungerer egentlig verifikasjon?
I denne konteksten ser vi kun på beslutningsproblemer. La oss si at du vil finne ut om det finnes en sti fra node $s$ til node $t$ i en graf $G=(V,E)$. Svaret er ja eller nei, så dette er et beslutningsproblem. Hvis det finnes en sti, så er det lett for meg å verifisere, dersom du viser meg en slik sti. Men svaret på problemet er jo bare «ja», i så fall; hvordan skal jeg kunne sjekke det uten at du også faktisk gir meg en løsning på det vanskeligere problemet som innebærer å faktisk finne en slik sti?
Situasjonen her er at vi stort sett bare er interesserte i om det er mulig å verifisere et ja-/nei-svar, dersom vi får en slik mer utførlig løsning, som vi gjerne kaller et sertifikat eller vitne. En verifikasjonsalgoritme $A(G,p)$ for dette sti-problemet kan altså ta inn en graf $G$ (med $s$ og $t$ identifiserte) og en sti $p$ og, sjekke at stien $p$ faktisk går fra $s$ til $t$. Det er ikke noe krav om at en beslutningsalgoritme skal kunne finne en slik sti $p$. For klassen NP, for eksempel, krever vi at et slikt sertifikat skal eksistere og at det skal eksistere en algoritme $A$ som kan benytte seg av det for å verifisere svaret.
Her er det viktig å merke seg at for NP krever vi bare at det skal finnes slike sertifikater dersom svaret er ja (og for co-NP, bare hvis svaret er nei).
Men det kan fortsatt være litt uklart hva det formelle forholdet mellom et beslutningsproblem og et sertifikat er. For sti-problemet vårt, for eksempel, må sertifikatet være en sti? Kunne det ikke være at det finnes andre måter å verifisere et ja-svar på?
Jo, det kan det. Og vi stiller ingen slike krav. Det vi krever er bare at verifikasjonsalgoritmen skal kunne verifisere korrekte ja-svar og ingen andre. Altså:
- En verifikasjonsalgoritme $A(x,y)$ for et språk $L$ tar inn en instans (bitstreng) $x$ og en annen bitstreng $y$, og gir ut $0$ eller $1$.
- Dersom $x\in L$ så skal det eksistere en bitstreng $y$ slik at $A(x,y)=1$.
- Dersom $x\notin L$ så skal det ikke eksistere noen slik bitstreng.
Det er det hele. Det er bitstrengen $y$ vi her kaller et sertifikat, men den trenger ikke ha noen spesielle egenskaper, annet enn at den får $A$ til å svare $0$ eller $1$ for en gitt $x$.
Merk også asymmetrien her: Selv om $x\in L$, så kan det finnes mange bitstrenger $y$ der $A(x,y)=0$. Vi krever bare at det skal finnes minst én der $A(x,y)=1$ – og at om $x\notin L$ så skal det ikke finnes noen slik $y$.