El problema de decisión
Dada una fórmula booleana , ¿tiene exactamente una asignación satisfactoria?ϕ
puede verse en , -hard y -hard. ¿Se sabe algo más sobre su complejidad?U P c o N P
El problema de decisión
Dada una fórmula booleana , ¿tiene exactamente una asignación satisfactoria?ϕ
puede verse en , -hard y -hard. ¿Se sabe algo más sobre su complejidad?U P c o N P
Su problema se conoce como el problema que es -complete. El problema está en pero no se sabe que es -duro bajo reducciones de tiempo polinomiales deterministas, donde la clase .U S D p D p D p = { L 1 ∩ ¯ L 2 ∣ L 1 , L 2 ∈ N P }
Papadimitriou y Yannakis [1] demostraron que el conjunto de fórmulas satisfactoriamente únicas está contenido en . Esto sigue por la definición de : que sea SAT y que sea el conjunto de fórmulas con o más tareas satisfactorias. Con respecto a -dureza de , Blass y Gurevich [2] dieron una respuesta parcial. Por un lado, mostraron que se necesitaría una técnica de prueba no relativizante para resolver la cuestión. Sin embargo, Valiant y Vazirani [3] dieron una reducción aleatoria del tiempo polinómico de muestra -dureza deD p L 1 L 2 2 D p ÚNICO-SATSAT D p ÚNICO-SAT bajo reducciones de tiempo polinomiales aleatorias.
Cuando se sabe que el problema tiene como máximo una tarea o ninguna, el problema de la promesa se llama . El teorema Valiant-Vazirani establece que si hay un algoritmo de tiempo polinomial para , entonces . Para demostrar su teorema, demostraron que el problema prometedor es -hard bajo reducciones de tiempo polinomiales aleatorias. Un corolario que se desprende del teorema de Valiant-Vazirani es que está completo para bajo reducciones de tiempo polinómicas aleatorias.UNAMBIGUOUS-SAT N P = R P UNAMBIGUOUS-SAT N P UNIQUE-SAT D p
[1] Papadimitriou, Christos H. y Mihalis Yannakakis. "La complejidad de las facetas (y algunas facetas de la complejidad)". Actas del decimocuarto simposio anual de ACM sobre Teoría de la informática. ACM, 1982.