Konsekuensi dari UP sama dengan NP

EDIT di 2011/02/08: Setelah beberapa referensi menemukan dan membaca, saya memutuskan untuk memisahkan pertanyaan asli menjadi dua yang terpisah. Inilah bagian tentang UP vs NP, untuk bagian kelas sintaksis dan semantik silakan lihat Manfaat untuk kelas sintaksis dan semantik .

$\mathsf{UP}$ (waktu polinomial yang jelas, lihatwikidankebun binatanguntuk referensi) didefinisikan sebagai bahasa yang diputuskan oleh$\mathsf{NP}$ -Mesin dengan penambahan kendala bahwa

• Paling tidak ada satu jalur komputasi yang menerima input apa pun.

Hubungan yang tepat antara $\mathsf{P}$ vs $\mathsf{UP}$ dan $\mathsf{UP}$ vs $\mathsf{NP}$ masih terbuka. Kita tahu bahwa fungsi satu arah kasus terburuk ada jika dan hanya jika $\mathsf{P} \neq \mathsf{UP}$ , dan ada nubuat relatif terhadap semua kemungkinan inklusi $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$ .

Saya tertarik mengapa $\mathsf{UP}$ vs $\mathsf{NP}$ adalah pertanyaan penting. Orang cenderung percaya (setidaknya dalam literatur ) bahwa dua kelas ini berbeda, dan masalah saya adalah:

Jika $\mathsf{UP} = \mathsf{NP}$ , apakah ada konsekuensi "buruk" yang terjadi?

Ada posting terkait di blog kompleksitas pada tahun 2003. Dan jika pemahaman saya benar, hasil dari Hemaspaandra, Naik, Ogiwara dan Selman menunjukkan bahwa jika

• Ada $\mathsf{NP}$ bahasa $L$ sehingga untuk setiap rumus satisfiable $\phi$ ada yang unik memuaskan tugas $x$ dengan $(\phi,x)$ di $L$ ,

kemudian hierarki polinomial runtuh ke tingkat kedua. Tidak ada implikasi seperti itu diketahui jika $\mathsf{UP} = \mathsf{NP}$ berlaku.

Hal ini diketahui bahwa menyiratkan S p a n P = # P sejak Kobler, Schoning, dan Toran membuktikan bahwa U P = N P jika dan hanya jika S p a n P = # P . Sangat mudah untuk melihat bahwa # P terkandung dalam S p a n P .$\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf {\#P}$$\mathsf {SpanP}$

Fungsi adalah dalam S p a n P jika ada N P Turing transduser mesin M sehingga untuk semua x , f ( x ) adalah jumlah output yang berbeda dari M pada input x .$f : Σ^* →\mathbb N$$\mathsf{SpanP}$$\mathsf {NP}$$M$$x$$f(x)$$M$$x$

J. Kobler, U. Schoning, dan J. Toran. Tentang penghitungan dan perkiraan , Acta Informatica, 26: 363-379, 1989.