Adakah masalah yang mudah dihitung tetapi sulit diverifikasi?

Dengan asumsi P NP, masalah NP-complete adalah "sulit untuk dipecahkan, tetapi memiliki jawaban yang mudah untuk diperiksa." Apakah masuk akal untuk mempertimbangkan yang sebaliknya, yaitu, masalah yang mudah untuk menghitung jawaban yang benar, tetapi sulit untuk memverifikasi solusi yang diakui sewenang-wenang? $\neq$

Saya pikir masalah seperti itu akan menyiratkan:

Secara eksponensial banyak jawaban "benar" untuk setiap masukan yang diberikan, karena jika tidak verifikasi dapat dilakukan hanya dengan menghitung semua jawaban yang benar.
Beberapa jawaban "benar" mudah untuk dihitung, tetapi yang lain sulit ditemukan.

complexity-theory rphv
sumber

Aku meragukan itu. Jika jawaban mudah dihitung, pilihan sertifikat mudah: berikan jawaban yang dimaksud dengan masalahnya, dan "periksa" jawabannya dengan memecahkan masalah, dan lihat apakah jawaban yang dimaksud sebenarnya adalah jawabannya.

Patrick87

@ Patrick87 - Saya rasa saya membahas ini dalam pertanyaan. Bagaimana dengan fungsi multi-nilai

yang mengaitkan sekumpulan nilai

dengan input

? Asumsikan bahwa

, dan mudah untuk memilih elemen dari

, tetapi mengingat

sulit untuk menentukan apakah

f

$f$

I_{f} (x) = {y_{1}, y_{2}, \dots}

$I_f(x) = \{y_1, y_2, \dots \}$

x

$x$

| I_{f} (x) | = 2^{| x |}

$|I_f(x)| = 2^{|x|}$

I_{f} (x)

$I_f(x)$

z

$z$

z \in I_{f} (x)

$z \in I_f(x)$

rphv

@ Patrick87 Solver mungkin deterministik dan hanya menghasilkan satu dari semua jawaban yang ada. Anda kemudian membutuhkan cara yang efisien untuk memeriksa apakah dua solusi itu setara. Bisakah kesetaraan pada set lebih sulit daripada memecahkan masalah?

Raphael

Aku benar-benar merindukan bagian itu, maaf. Tetap saja, saya cenderung meragukan premisnya. Saya akan memikirkannya sedikit lagi dan kembali jika saya memiliki pemikiran yang lebih relevan.

Patrick87

Sebuah sertifikat biasanya berarti bahwa ada cara mudah untuk merekonstruksi bukti, jadi menurut definisi jika Anda memberikan sertifikat verifikasi mudah. Solusi tanpa sertifikat mungkin sulit.

Gilles 'SO- stop being evil'

Jawaban:

Jika Anda baik-baik saja dengan masalah buatan, Anda dapat membuatnya banyak. Berikut ini beberapa di antaranya:

Dengan bilangan bulat positif n di unary, jawab rumus 3CNF yang memuaskan dalam n variabel Boolean.
Memberikan satu formula 3CNF yang memuaskan itu mudah, tetapi memutuskan apakah formula 3CNF yang diberikan memuaskan atau tidak adalah 3SAT, masalah NP-complete yang terkenal.
Tidak ada input. Jawab saja mesin Turing yang berhenti (saat dijalankan dengan pita input kosong).
Memberikan satu mesin Turing seperti itu mudah, tetapi apakah mesin Turing yang diberikan berhenti atau tidak, tidak dapat dipastikan.

Ditambahkan : Omong-omong, saya tidak berpikir bahwa apa yang Anda tulis dalam paragraf terakhir berlaku:

Saya pikir masalah seperti itu akan menyiratkan banyak jawaban "benar" secara eksponensial untuk setiap masukan yang diberikan, karena jika tidak verifikasi dapat dilakukan dengan hanya menghitung semua jawaban yang benar.

Jika masalah memiliki satu solusi, maka memang memeriksa sebuah jawaban tidak lebih sulit daripada menghitung solusi yang benar. Namun, jika masalahnya memiliki satu solusi mudah dan satu solusi sulit, maka Anda tidak dapat menghitung semua solusi secara efisien. Berikut adalah salah satu masalah (yang sangat buatan):

Diberikan mesin Turing M , jawab salah satu pernyataan berikut yang benar: " M berhenti pada pita input kosong," " M tidak berhenti pada pita input kosong," dan " M adalah mesin Turing."
Memberikan satu solusi itu mudah : Anda selalu dapat memilih " M adalah mesin Turing." Namun, apakah jawaban yang diberikan benar atau tidak tidak dapat diputuskan. Perhatikan bahwa dalam masalah ini, hanya ada dua solusi untuk setiap instance.

Tsuyoshi Ito
sumber

Adakah cara yang masuk akal untuk mendefinisikan secara formal apa artinya masalah seperti itu menjadi "buatan"? (Dengan "masuk akal", maksud saya sesuatu yang dapat kita setujui secara luas, seperti mengatakan bahwa definisi "dapat dihitung" menangkap intuisi kita tentang apa artinya itu.)

Gilles 'SO-stop being evil'

@Gilles: Tidak, saya kira tidak. Saya menyebut masalah ini "buatan" karena sangat tidak mungkin seseorang menemukan masalah ini terlebih dahulu dan kemudian menemukan bahwa mudah untuk membuat satu jawaban dan sulit untuk memutuskan kebenaran dari calon jawaban yang diberikan. Tetapi "kesemuan" ini sama sekali bukan gagasan yang keras.

Tsuyoshi Ito

@ Tsuyoshi Ito - Terima kasih atas jawaban Anda yang jelas. Saya telah mengedit paragraf terakhir untuk mencerminkan wawasan Anda.

rphv

Meskipun jawaban Tsuyoshi Ito mencakup jawaban "utama", ada dua catatan yang lebih halus yang ingin saya tambahkan.

Bahkan ketika solusinya sulit untuk diverifikasi, memeriksa solusinya masih mudah diperiksa dengan string bukti pendek. Yaitu, dengan memperluas solusi sedikit dengan informasi tambahan, itu menjadi mudah diperiksa; verifikasi selalu dalam NP. Salah satu cara untuk melihat ini adalah bahwa agen yang menghitung suatu solusi dapat merekam semua bit acak yang mereka gunakan, dan kemudian verifier dapat menggunakan string acak yang sama untuk menjalankan perhitungan yang sama. (Pepatah harus menggunakan bit acak, jika tidak mereka selalu menampilkan jawaban yang sama, dan pemverifikasi selalu dapat dengan mudah memeriksa dengan menghitung jawaban dengan metode yang sama.)
Untuk komputer kuantum, ini adalah pertanyaan yang sangat terbuka. Untuk komputer klasik, verifier selalu dapat melakukan sesuatu seperti mensimulasikan prover dan memeriksa apakah mereka mendapatkan jawaban yang sama. Sangat mungkin bahwa untuk beberapa masalah rumit, ada algoritma kuantum yang menghasilkan distribusi yang seragam di semua (secara eksponensial banyak) solusi, yang sulit untuk diverifikasi. Anda tidak dapat menjalankan ulang prover, karena kemungkinan besar Anda akan mendapatkan jawaban yang berbeda setiap kali.

Sebagai contoh dari jenis masalah yang serupa, masalah Deutsch-Jozsa sedikit menderita dari ini. Jika oracle bukan fungsi yang seimbang, maka komputer kuantum dapat dengan cepat menentukan bahwa ini yang terjadi, tetapi tidak ada bukti singkat yang memungkinkan komputer klasik untuk memverifikasi ini. (Ini hanya masalah "mirip" karena masih bisa diperiksa oleh komputer kuantum lain, dan pengecekan juga dalam BPP klasik bahkan jika tidak dalam P.)

Alex Meiburg
sumber