Abstrakte problemer

Et abstrakt beslutningsproblem, $Q$, er en Binærrelasjon mellom mengden av alle instanser, $I$, og mengden av alle løsninger $S=\{0,1\}$.

---

Eksempel

For korteste-vei eksempelet mellom to noder vil en instans være på formen $i=(G,u,v,k)\in I$, og løsningen er enten ja (1) eller nei (0).

Outputten vår er nå binær, men vi ønsker å også at inputten vår skal være binær. Derfor bruker vi Enkoding.