UP (clase de complejidad)

En teoría de la complejidad computacional, la clase de complejidad UP (tiempo polinómico, no-determinista, no-ambiguo) es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no-determinista tal que la solución si existe es única. La clase UP está contenida en NP y contiene a P. No se sabe si estas inclusiones son estrictas.

Un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico con dos entradas y una constante c tal que:

L = {x in {0,1}* | ∃! valor, y con |y| = O(|x|^c) tal que A(x,y) = 1}