UP

Keywords: UP, BQP, Clase de complejidad, Co-NP, Co-NP-completo, Complejidad computacional, Cota superior asintótica, EXPSPACE

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}

clases de complejidad más importantes

L | NL | P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH

Keywords: UP, BQP, Clase de complejidad, Co-NP, Co-NP-completo, Complejidad computacional, Cota superior asintótica, EXPSPACE