UP (complejidad)

En la teoría de la complejidad , UP ( unambiguous non-deterministic polynomial-time ) es la clase de complejidad de problemas de decisión que se pueden resolver en tiempo polinomial en una máquina de Turing unambigua (una máquina de Turing no determinista con como máximo una ruta de aceptación para cada entrada). UP contiene P y está contenido en NP .

Una reformulación común de NP establece que un lenguaje pertenece a NP si y solo si un "certificado" dado puede ser verificado por una máquina determinista en tiempo polinomial. De manera similar, un lenguaje pertenece a UP si un certificado dado puede ser verificado en tiempo polinomial, y la máquina verificadora solo acepta como máximo un certificado para cada instancia del problema. ^{[ 1 ]} Más formalmente, un lenguaje L pertenece a UP si existe un algoritmo A de dos entradas en tiempo polinomial y una constante c tal que

si${\displaystyle x\in L}$, entonces existe un certificado único y con${\displaystyle |y|=O(|x|^{c})}$de tal manera que${\displaystyle A(x,y)=1}$⁠

si${\displaystyle x\not \in L}$, no hay certificado y con${\displaystyle |y|=O(|x|^{c})}$de tal manera que${\displaystyle A(x,y)=1}$⁠

El algoritmo A verifica L en tiempo polinomial.

UP (y su complemento co-UP ) contienen tanto el problema de factorización de enteros como el problema del juego de paridad . Dado que aún no se ha realizado un esfuerzo decidido para encontrar una solución en tiempo polinomial para ninguno de estos problemas, se sospecha que será difícil demostrar que P = UP , o incluso P = ( UP ∩ co-UP ).

El teorema de Valiant-Vazirani establece que NP está contenido en RP ^Promise-UP , lo que significa que hay una reducción aleatoria de cualquier problema en NP a un problema en Promise-UP .

No se sabe que UP tenga problemas graves . ^{[ 2 ]}