En la teoría de la complejidad , UP ( tiempo polinomial no determinista inequívoco ) es la clase de complejidad de problemas de decisión que se pueden resolver en tiempo polinómico en una máquina de Turing inequívoca 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 está en NP si y solo si una respuesta dada puede ser verificada por una máquina determinista en tiempo polinomial. De manera similar, un idioma está en UP si una respuesta dada se puede verificar en tiempo polinomial, y la máquina verificadora solo acepta como máximo una respuesta para cada instancia de problema. Más formalmente, un lenguaje L pertenece a UP si existe un algoritmo A de tiempo polinómico de dos entradas y una constante c tal que
- si x en L , entonces existe un certificado único y con tal que
- si x no está en L , no hay certificado y con tal que
- 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 ; Debido a que un esfuerzo determinado aún tiene que encontrar una solución de tiempo polinómico para cualquiera de estos problemas, se sospecha que es difícil mostrar 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 .
Referencias
Referencias
- Lane A. Hemaspaandra y Jorg Rothe, Computación inequívoca: jerarquías booleanas y conjuntos completos de Turing dispersos , SIAM J. Comput., 26 (3) (junio de 1997), 634–653