Bukti apa yang kita miliki untuk

Mengikuti saran Josh Grochow, saya mengubah komentar saya dari pertanyaan sebelumnya menjadi pertanyaan baru.

Bukti apa yang kita miliki untuk ?$\mathsf{UP} \neq \mathsf{NP}$

Berikut $\mathsf{UP}$ adalah kelas bahasa dikenali oleh waktu non-deterministik mesin Turing polinomial yang memiliki jalur menerima unik pada "ya" contoh dan tidak ada menerima path pada "tidak" contoh.

Jelas , tapi mengapa kita akan percaya bahwa penahanan yang ketat? Bukti yang saya dapat menemukan adalah pemisahan oracle : tunduk pada oracle acak, P ⊊ U P ⊊ N P . Juga, Kebun Binatang Kompleksitas menunjukkan bahwa U P tidak diyakini memiliki masalah lengkap.$\mathsf{UP} \subseteq \mathsf{NP}$$\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$$\mathsf{UP}$

Bahkan, Selman, dan Yacobi menduga bahwa ada tidak ada seorang beririsan -pair ( A , B ) sehingga semua pemisah dari ( A , B ) adalah ≤ p T -Hard untuk N P . Dugaan ini menyiratkan bahwa U P ≠ N P .$NP$$(A, B)$$(A, B)$$\le_T^p$$NP$$UP \ne NP$

S. Even, A. Selman, dan J. Yacobi. Kompleksitas masalah janji dengan aplikasi ke kriptografi kunci publik. Informasi dan Kontrol, 61: 159–173, 1984.