Complejidad de decidir si una fórmula tiene exactamente 1 tarea satisfactoria

11

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Δ2UPcoNP

sdcvvc
fuente

Respuestas:

11

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 2L 1 , L 2N P }UNIQUE-SATUSDpDpDp={L1L2¯L1,L2NP}

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-SATDpDpL1L22DpUNIQUE-SATSATDpUNIQUE-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 pUNAMBIGUOUS-SATUNAMBIGUOUS-SATNP=RPUNAMBIGUOUS-SATNPUNIQUE-SATDp


[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.

[2] Blass, Andreas y Yuri Gurevich. "Sobre el único problema de satisfacción". Información y control 55.1 (1982): 80-88.

[3] Valiant, Leslie G. y Vijay V. Vazirani. "NP es tan fácil como detectar soluciones únicas". Informática teórica 47 (1986): 85-93.

Juho
fuente
Gracias por la respuesta; También encontré un capítulo en un libro que decía que la existencia de una reducción determinista está abierta.
sdcvvc