Intuisi untuk kelas UP

Kelas UP didefinisikan sebagai:

Kelas masalah keputusan dipecahkan oleh mesin NP sedemikian rupa

Jika jawabannya adalah 'ya,' tepat satu jalur perhitungan menerima.

Jika jawabannya adalah 'tidak,' semua jalur perhitungan ditolak.

Saya mencoba mengembangkan intuisi untuk definisi ini.

Dapatkah seseorang mengatakan bahwa masalah UP adalah masalah dengan solusi unik (misalnya factorisation utama)?

Itu tampaknya dekat dengan kebenaran bagi saya; tetapi saya tidak dapat menahan diri untuk berpikir bahwa itu berarti, karena UP mengandung P dan terkandung dalam NP, bahwa jika P = NPkita mendapatkan itu P = UP = NP, maka semua masalah dalam NPmemiliki solusi unik juga, yang tampaknya seperti sesuatu yang terbukti tidak benar: P != NPoleh reductio ad absurdum. Saya harap tidak ada terlalu banyak dugaan dan isyarat tangan dalam paragraf ini untuk selera Anda.

Kebingungan Anda tampaknya disebabkan oleh fakta bahwa masalah memiliki lebih dari satu cara untuk mendefinisikan "solusi" (atau saksi). Jenis solusi bukan bagian dari definisi masalah. Misalnya, untuk pewarnaan grafik, jenis solusi yang jelas adalah penugasan satu warna untuk setiap simpul (menggunakan paling banyak jumlah warna yang diperlukan); Namun, oleh teorema Gallai-Hasse-Roy-Vitaver$\mathsf{NP}$jenis solusi lain yang bekerja sama baiknya adalah penugasan orientasi ke setiap sisi (menciptakan jalur terarah paling banyak jumlah simpul yang diperlukan). Kedua jenis solusi ini keduanya dapat diperiksa dalam waktu polinomial, tetapi dengan algoritma yang berbeda, dan mereka juga memiliki sifat kombinatorial yang berbeda. Misalnya, untuk contoh masalah yang khas, jumlah penetapan warna titik akan berbeda dari jumlah orientasi tepi. Banyak penelitian tentang mempercepat algoritma eksponensial untuk masalah tipe NP dapat diartikan sebagai menemukan keluarga solusi baru untuk masalah yang sama yang memiliki lebih sedikit kemungkinan untuk diperiksa.

Setiap masalah di memiliki "solusi" yang hanya terdiri dari string kosong. Untuk memverifikasi bahwa ini adalah solusi, cukup periksa bahwa string solusi kosong dan kemudian jalankan algoritma waktu polinomial untuk contoh masalah. Dengan jenis solusi ini, setiap instance ya memiliki tepat satu solusi yang valid dan setiap instance tidak memiliki nol, memenuhi definisi dan menunjukkan bahwa . Jika maka solusi string kosong yang sama juga akan bekerja untuk setiap masalah di , menunjukkan bahwaN P U P P ⊂ U P P = N P N P N P = U $\mathsf{P}$$\mathsf{NP}$$\mathsf{UP}$$\mathsf{P}\subset\mathsf{UP}$$\mathsf{P}=\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP}=\mathsf{UP}$. Jadi tidak ada kontradiksi antara fakta bahwa solusi string kosong adalah unik dan fakta bahwa beberapa jenis solusi lain untuk masalah yang sama adalah non-unik.

Saya setuju dengan komentar Shaull bahwa intuisi memiliki saksi yang unik adalah benar, tetapi halus. Argumen dalam paragraf terakhir Anda dapat dibuat secara teknis tepat, dan menyoroti kehalusan versus . Secara khusus, masalah pada paragraf terakhir Anda pada dasarnya adalah pertanyaan apakah :N P N P M V ⊆ c N P S $\mathsf{UP}$$\mathsf{NP}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

N $\mathsf{NPMV}$ adalah kelas fungsi multi-nilai parsial yang dihitung dalam waktu polinomial non-deterministik, yaitu, setiap cabang yang menerima non-deterministik dapat menghasilkan nilai (jika tidak ada jalur penerimaan pada beberapa input, maka tidak ada output , mengarah pada fakta bahwa ini hanya perlu fungsi parsial ). Ini terkait erat dengan versi pencarian dari masalah .$\mathsf{NP}$

N P M $\mathsf{NPSV}$ adalah kelas fungsi bernilai- tunggal di , yaitu, beberapa cabang dapat menerima, tetapi jika cabang mana pun menerima, semua cabang yang menerima harus mengeluarkan nilai yang sama.$\mathsf{NPMV}$

Secara intuitif, paragraf terakhir Anda berbicara tentang apakah Anda selalu dapat memilih atau tidak, dari antara saksi untuk verifikasi tertentu dari beberapa masalah , seorang saksi tunggal. Ini adalah pertanyaan apakah setiap function memiliki penyempurnaan (dilambangkan ). Jika ini masalahnya, maka hierarki polinomial runtuh (lihat Hemaspaandra, Naik, Ogihara, dan Selman "Solusi Komputasi yang Unik Menghancurkan Hirarki Polinomial" ).N P M V N P S V N P M V ⊆ c N P S $\mathsf{NP}$$\mathsf{NPMV}$$\mathsf{NPSV}$$\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

Berbeda dengan , tidak ada implikasi yang diketahui mengikuti dari . Pada dasarnya karena mengingat bahasa , yang (saksi untuk) mesin untuk membutuhkan tidak ada hubungannya dengan (saksi untuk) lainnya mesin (s ) untuk .N P = U P L ∈ N P U P L N P$\mathsf{UP}$$\mathsf{NP} = \mathsf{UP}$$L \in \mathsf{NP}$$\mathsf{UP}$$L$$\mathsf{NP}$$L$