- UP (complejidad)
-
UP (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}
Categoría: Clases de complejidad
Wikimedia foundation. 2010.