Si l'on montre que k-SAT UNIQUE est en P, cela implique-t-il P = NP?

9

Valiant et Vazirani ont prouvé que la SAT est réductible à la SAT UNIQUE sous des réductions probabilistes randomisées du temps polynomial. Calabro et al . a montré que UNIQUE k-SAT est aussi dur que k-SAT. Maintenant, la question est, si quelqu'un montre que k-SAT UNIQUE est dans P, cela implique-t-il P = NP?

Références

  1. LG Valiant et VV Vazirani, "NP est aussi simple que de détecter des solutions uniques." Informatique théorique 47: 85–93, 1986. ( PDF sur ScienceDirect.)

  2. C. Calabro, R. Impagliazzo, V. Kabanets et R. Paturi, "La complexité de k-SAT unique: un lemme d'isolement pour les k-CNF". Journal of Computer and System Sciences 74 (3): 386–393, 2008. ( PDF à la bibliothèque numérique ACM; PDF gratuit .)

Husrev
la source
NP

Réponses: