Jika seseorang menunjukkan bahwa UNIQUE k-SAT ada di P, apakah itu menyiratkan P = NP?

Valiant & Vazirani membuktikan bahwa SAT dapat direduksi menjadi SAT UNIK di bawah pengurangan probabilistik acak dalam waktu polinomial. Calabro et al . menunjukkan bahwa UNIK k-SAT sama sulitnya dengan k-SAT. Sekarang pertanyaannya adalah, jika seseorang menunjukkan bahwa UNIK k-SAT ada di P, apakah itu menyiratkan P = NP?

Referensi

1. LG Valiant dan VV Vazirani, "NP semudah mendeteksi solusi unik." Ilmu Komputer Teoritis 47: 85–93, 1986. ( PDF on ScienceDirect.)

2. C. Calabro, R. Impagliazzo, V. Kabanets dan R. Paturi, "Kompleksitas unik k-SAT: Lemma Isolasi untuk k-CNF". Jurnal Ilmu Komputer dan Sistem 74 (3): 386–393, 2008. ( PDF di ACM Digital Library; PDF gratis )

Ini masih merupakan pertanyaan terbuka; UP tidak diketahui setara dengan NP . Dalam makalah "NP Mungkin Tidak Semudah Mendeteksi Solusi Unik," Beigel, Burhman dan Fortnow membangun oracle di mana P berisi UP tetapi P masih tidak setara dengan NP .