Enkoding

En funksjon som gjør abstrakte objekter til binærstrenger. Vi kan si at vi enkoder et abstrakt problem, $Q$, til et konkret problem, $e(Q)$, ved å kunne enkode alle mulige instanser i $Q$.

---

Eksempel

I korteste vei eksempelet kan en enkoding foregå slik

$$(G,u,v,k)\stackrel{\text{ce}Enkoding}{\to }0110100\dots 01=i$$

Etter vi har enkodet instansen til en binærstreng, kan vi snakke om kjøretid

$$n=|i|$$

Et konkret problem er derfor løsbar i Polynomisk tid dersom det finnes en algoritme som kan løse problemet i $O(n^p)$ tid for en konstant $p$.