Wenn man zeigt, dass UNIQUE k-SAT in P ist, bedeutet das P = NP?

9

Valiant & Vazirani haben bewiesen, dass SAT unter randomisierten probabilistischen Verkürzungen der Polynomzeit auf EINZIGARTIGES SAT reduzierbar ist. Calabro et al . zeigten, dass EINZIGARTIGES k-SAT so hart ist wie k-SAT. Die Frage ist nun, wenn jemand zeigt, dass UNIQUE k-SAT in P ist, impliziert dies P = NP?

Verweise

  1. LG Valiant und VV Vazirani: "NP ist so einfach wie das Erkennen einzigartiger Lösungen." Theoretical Computer Science 47: 85–93, 1986. ( PDF on ScienceDirect.)

  2. C. Calabro, R. Impagliazzo, V. Kabanets und R. Paturi, "Die Komplexität von einzigartigem k-SAT: Ein Isolations-Lemma für k-CNFs". Journal of Computer and System Sciences 74 (3): 386–393, 2008. ( PDF in der ACM Digital Library; kostenloses PDF .)

Husrev
quelle
Valiant & Vazirani zeigten, dass SAT unter RP-Reduktionen auf UNAMBIGUOUS SAT reduzierbar ist. Im zweiten Fall sprechen Sie von UNIQUE SAT, das -hard ist. NP
Rus9384

Antworten: