Transformació polinòmica

En complexitat computacional, una transformació polinòmica, reducció polinòmica o reducció de Karp, és una manera de relacionar dos problemes de decisió, de manera que l'existència d'un algoritme que resol el primer problema, garantisa immediatament, i a través d'un temps polinòmic, l'existència d'un algoritme que resol el segon.

Formalment, siguen L i M llenguages formals sobre els alfabets Σ i Γ, respectivament, una transformació polinòmica de L en M és una funció computable:

$f:{\Sigma }^{*}\to {\Gamma }^{*}$

que pot ser calculada en temps polinòmic en funció del tamany de l'entrada, i que està definida per:

$w\in L\iff f(w)\in M$

per a tot element w de Σ^*.

Quan esta funció f existix, es diu que "L és polinómicamente transformable en M".

Aplicació

L'idea de reduir problemes en uns atres s'utilisa comunament en la classificació de problemes en vàries classes de complexitat, tals com NP-complet, PSPACE-complet i EXPTIME-complet.