El problema es coNP -hard; puede reducir fácilmente el problema UNSAT a este problema.
Una caracterización más precisa es que el problema es C = P -completo. De hecho, una definición de la clase C = P es que es la clase de problemas que son muchas veces polinomiales reducibles a este mismo problema (por lo general, esta definición se establece en términos de funciones GapP ). Pero como esto no dice mucho, déjame definir esta clase de otra manera.
Sea C = P la clase de problemas que son polinomiales en tiempo múltiple reducibles al siguiente problema: dado un circuito booleano φ y un entero K (en binario), decida si el número de asignaciones satisfactorias de φ es igual a K . Mediante una reducción estándar que muestra la completitud # P de # 3SAT, podemos restringir φ para que sea una fórmula 3CNF sin afectar la clase. La clase C = P contiene una clase llamada US , que contiene UP y coNP.
Con esta definición, su problema es C = P-completo. En realidad, la dureza C = P es fácil de ver a partir de la definición de la clase C = P (que usa fórmulas 3CNF).
Para probar la membresía en C = P, suponga que debemos decidir si dos fórmulas CNF φ 1 y φ 2 tienen el mismo número de asignaciones satisfactorias o no. Sin pérdida de generalidad, podemos suponer que las dos fórmulas tienen el mismo número de variables, digamos n . Construya un circuito booleano φ que tome n +1 bits como entrada para que el número de asignaciones satisfactorias de φ sea igual a c 1 + (2 n - c 2 ), donde c 1 y c 2sean los números de asignaciones satisfactorias de φ 1 y φ 2 , respectivamente. Entonces el número de asignaciones satisfactorias de φ es igual a 2 nsi y solo si c 1 = c 2 .
Aquí hay una pequeña variación de la pregunta original. Sea un oráculo que, en la entrada ( f 1 , f 2 ) emite 1 si CNF f 1 tiene más soluciones que CNF fO (f1,f2) f1 .f2
Dado este oráculo, construimos una máquina de poli-tiempo que puede resolver el problema # P-completo de calcular el número de soluciones para un CNF dado φ . Tenga en cuenta que eso φM φ φ puede tener un número exponencial de soluciones.
funciona de la siguiente manera: genera fórmulas con un número conocido de soluciones, y mediante la búsqueda binaria y al hacer consultas polinomiales como máximo a O , encuentra una fórmula φ i que tieneel mismonúmero de soluciones que φ . Finalmente genera la cantidad de soluciones que acabamos de encontrar.M O φi φ
Esto muestra que tiene complejidad #P.MO
fuente
It seems like it's atleast NP-hard as one can easily construct a SAT formula with just one solution. Then by the Valiant-Vazirani theorem, there's a probabilistic reduction from every SAT formula to a set of Unique-SAT problems (determining whether a formula has a unique solution) and comparing those Unique-SAT problems with the constructed SAT formula with just one solution enables you to determine the satisfiability of the SAT formula under consideration.
fuente