La clase de complejidad consiste en esos problemas que pueden decidirse por una máquina de Turing no determinista de tiempo polinomial que tiene como máximo una ruta computacional de aceptación. Es decir, la solución, si la hay, es única en este sentido. Se cree altamente improbable que todos los...
El teorema de Valiant-Vazirani dice que si hay un algoritmo de tiempo polinómico (determinista o aleatorio) para distinguir entre una fórmula SAT que tiene exactamente una asignación satisfactoria y una fórmula insatisfactoria, entonces NP = RP . Este teorema se demuestra mostrando que UNIQUE-SAT...
Considere el siguiente problema: dada una fórmula CNF y una asignación que satisface esta fórmula, ¿hay otra asignación satisfactoria para esta fórmula? ¿Cuál es la complejidad de este problema? (Seguramente está en NP, pero ¿también es NP-hard?) ¿Qué sucede si no se le asigna la tarea y solo...
EDITAR el 2011/02/08: Después de encontrar y leer algunas referencias, decidí separar la pregunta original en dos. Aquí está la parte relativa a UP vs NP, para la parte de clases sintácticas y semánticas, consulte Beneficios para clases sintácticas y semánticas . (el tiempo polinómico...
Estoy tratando de averiguar si hay resultados generales o ejemplos sobre la completitud NP del problema de encontrar una segunda solución a un problema NP-completo. Más precisamente, estoy interesado en cualquier problema de la siguiente forma: Dada una solución a una instancia I de un problema...
Siguiendo la sugerencia de Josh Grochow, estoy convirtiendo mi comentario de una pregunta anterior en una nueva pregunta. ¿Qué evidencia tenemos para ?U P ≠ N PUP≠NP\mathsf{UP} \neq \mathsf{NP} Aquí, U PUPAG\mathsf{UP} es la clase de lenguajes reconocibles por las máquinas de Turing no...
Preámbulo. La clase de complejidad AM son aquellos problemas que pueden resolverse mediante un sistema de prueba interactivo de dos rondas entre un probador "Merlin" y un verificador "Arthur". Un problema, que prueba alguna propiedad de un objeto X , está en AM si: Para casos de SÍ , para un...
Recientemente estuve leyendo un artículo muy bueno de Valiant y Vazirani que muestra que si , entonces no puede haber un algoritmo eficiente para resolver SAT incluso bajo la promesa de que es insatisfactorio o tiene una solución única. De este modo, se demuestra que SAT no admite un algoritmo...
El problema de la "Segunda " es el problema de decidir la existencia de otra solución diferente de alguna solución dada para la instancia del problema.XXX Para algunos problemas de -completo, la segunda versión de la solución es N P -completa (decidir la existencia de otra solución para el...