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

9

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

  1. LG Valiant y VV Vazirani, "NP es tan fácil como detectar soluciones únicas". Theoretical Computer Science 47: 85–93, 1986. ( PDF en ScienceDirect.)

  2. 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 ).

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. NP
rus9384

Respuestas: