En teoría de la complejidad , UP ( unambiguous non-deterministic polynomial-time ) es la clase de complejidad de problemas de decisión resolubles en tiempo polinomial 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 lenguaje está en UP si una respuesta dada puede ser verificada en tiempo polinomial, y la máquina verificadora solo acepta como máximo una respuesta para cada instancia del problema. Más formalmente, un lenguaje L pertenece a UP si existe un algoritmo de tiempo polinomial de dos entradas A y una constante c tal que
UP (y su complemento co-UP ) contienen tanto el problema de factorización de números enteros como el problema del juego de paridad . Debido a que aún no se ha realizado un esfuerzo determinado para encontrar una solución en tiempo polinomial para ninguno de estos problemas, se sospecha que es 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 ningún problema completo . [1]
