Reduksjon ved formelle språk

Et språk, $L_1$, er polynomisk redusibelt til $L_2$ dersom det eksisterer en polynomisk-tid beregnende funksjon,

$$f:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$$

s.a $x\in L_1$ $\leftrightarrow$ $f(x)\in L_2$.

Altså, hvis vi har en algoritme som bestemmer $L_2$ kan vi bruke $f$ til å bestemme $L_1$.

Dette kan vi gjøre ved å sjekke om alle mulige binærstrenger, $x$, er i $L_1$ ved å først beregne $f(x)$ i polynomisk tid, for å deretter sjekke om $f(x)\in L_2\leftrightarrow x\in L_1$.

• Dersom $L_2\in P$ vil sistnevnte ta polynomisk tid, og dermed er $L_1\in P$ også.