Si uno muestra que k-SAT ÚNICO está en P, ¿implica P = NP?

Valiant y Vazirani probaron que SAT es reducible a SAT ÚNICO bajo reducciones probabilísticas aleatorias en tiempo polinómico. Calabro y col . demostró que k-SAT ÚNICO es tan difícil como k-SAT. Ahora la pregunta es, si alguien muestra que k-SAT ÚNICO está en P, ¿implica P = NP?

Referencias

LG Valiant y VV Vazirani, "NP es tan fácil como detectar soluciones únicas". Theoretical Computer Science 47: 85–93, 1986. ( PDF en ScienceDirect.)
C. Calabro, R. Impagliazzo, V. Kabanets y R. Paturi, "La complejidad de k-SAT único: un lema de aislamiento para k-CNF". Journal of Computer and System Sciences 74 (3): 386–393, 2008. ( PDF en la Biblioteca Digital de ACM; PDF gratis ).

complexity-theory satisfiability p-vs-np Husrev
fuente

Valiant y Vazirani demostraron que SAT es reducible a SAT UNAMBIGUOUS bajo reducciones de RP. En el segundo caso, está hablando de SAT ÚNICO que es -hard.

N P

$\mathsf{NP}$

rus9384

Respuestas:

Esta sigue siendo una pregunta abierta; No se sabe que UP sea equivalente a NP . En el documento "NP podría no ser tan fácil como detectar soluciones únicas", Beigel, Burhman y Fortnow construyen un oráculo bajo el cual P contiene UP pero P aún no es equivalente a NP .

Kyle Jones
fuente