Verifikasjonsalgoritme

En algoritme, $A(x,y)$, som tar inn en instans $x$ i tillegg til et sertifikat,$y$, for å verifisere $x$.

---

Vi så i NP problem at det holdt å kunne verifisere et forslag til en løsning i polynomisk tid.

$$\downarrow$$

I Hamiltonian cycle problemet (HAM-CYCLE) vil

• $x$ være den binært enkodet, rettede grafen, $G$
• $y$ være tupelen med nodene i rekkefølge (også enkodet). Da kan vi si at $A(x,y)$ verifiserer $x$ dersom det eksisterer et sertifikat $y$ s.a $A(x,y)=1$.