Formelle språk

Basert på Språkteori for NPC problemer kan vi nå gi et konkret eksempel.

Vi sier at en algoritme $A:\{0,1{\}}^{\ast }\to \{0,1\}$ aksepterer en binærstreng $x\in \{0,1{\}}^{\ast }$ dersom $A(x)=1$, og avviser hvis $A(x)=0$.