Kodierungslänge

Ist die Größe oder auch Länge einer Instanz. Die Anzahl der notwendigen Bits für eine Binärdarstellung der Instanz.

Für natürliche und ganze Zahlen:

$$\begin{array}{ll}⟨n⟩=\lceil {\log }_2(n+1)\rceil & \text{ fu¨r }n\in \mathbb{N}\\ ⟨n⟩=\lceil {\log }_2(|n|+1)\rceil +1& \text{ fu¨r }n\in \mathbb{Z}\end{array}$$

Für rationale Zahlen: $⟨r⟩=⟨p⟩+⟨q⟩$