Apa perbedaan antara "Keputusan" dan "Verifikasi" dalam teori kompleksitas?

Dalam Teori Komputasi Michael Sipser di halaman 270 ia menulis:

P = kelas bahasa yang keanggotaannya dapat diputuskan dengan cepat.
NP = kelas bahasa yang keanggotaannya dapat diverifikasi dengan cepat.

Apa perbedaan antara "memutuskan" dan "diverifikasi"?

Tugas menentukan keanggotaan adalah: diberikan input $x$ , tentukan apakah $x \in L$ , yaitu hitung fungsi berikut:

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

Di sisi lain, tugas verifikasi keanggotaan adalah: diberikan setiap masukan dan (diusulkan) bukti (atau saksi ) dari keanggotaan, periksa cepat cuaca x ∈ L oleh bukti bahwa ¹.$x$$x\in L$

Sebagai contoh, pertimbangkan factorisation prima. Dengan , hitung semua faktor prima dari n . Di sisi lain, diberikan ( n , { i 1 , ... , i k } ) , verifikasi bahwa ∏ k j = 1 i j = n . Mana yang lebih mudah?$n \in \mathbb{N}$$n$$(n, \{i_1, \dots, i_k\})$$\prod_{j=1}^k i_j = n$

Contoh lain: Diberikan grafik berbobot , tentukan apakah ada lingkaran Hamilton (yang mengunjungi semua node) dengan bobot paling banyak k . Di sisi lain, diberikan ( G , ( v 1 , ... , v n ) ) , verifikasi apakah jalan v 1 → ⋯ → v n mengunjungi semua node tepat sekali dan memiliki bobot paling banyak k . Mana yang lebih sulit?$G = (V,E)$$k$$(G, (v_1, \dots, v_n))$$v_1 \to \dots \to v_n$$k$

1. Jadi Anda akan mengatakan "tidak" jika tetapi buktinya salah. Namun, itu baik-baik saja, ketika kita mempertimbangkan mesin nondeterministik dalam konteks ini; hanya penting bahwa kita dapat menebak bukti yang benar dan memverifikasinya (dengan cepat).$x \in L$

Jika kita mengabaikan masalah efisiensi, ada contoh lain yang menggambarkan perbedaan dengan analogi. Kita tahu bahwa masalah penghentian tidak dapat ditentukan: diberikan kode untuk mesin Turing, tidak ada cara yang efektif untuk menentukan apakah mesin berhenti jika dijalankan tanpa input.$e$

Tapi jika mesin tidak berhenti, tidak sulit untuk membuktikan kepada orang lain: hanya memberitahu mereka berapa banyak langkah mesin berjalan sebelum berhenti. Mereka dapat menjalankan mesin untuk banyak langkah dan tahu jika Anda mengatakan yang sebenarnya (tentu saja mengabaikan efisiensi).

Jadi set mesin Turing menghentikan tidak decidable, tetapi diverifikasi. Perhatikan bahwa tidak ada bukti harus diberikan untuk mesin yang tidak berhenti. Verifikasi asimetris dalam arti bahwa hanya keanggotaan di set memiliki diverifikasi, keanggotaan keluar dari himpunan tidak.

Situasi dengan P dan NP analog. Sebuah bahasa dalam NP jika ada sistem bukti sehingga setiap objek yang ada di bahasa memiliki bukti singkat (dibatasi oleh polinomial dalam ukuran objek) yang dapat diverifikasi secara efisien (dengan sejumlah langkah yang dibatasi oleh polinomial dalam ukuran input).

Di sisi lain, bahasa dalam P jika ada cara untuk mengetahui apakah objek yang arbitrer dalam atau tidak dalam bahasa menggunakan sejumlah langkah yang dibatasi oleh polinomial dalam ukuran objek. Sekarang kita perlu khawatir tentang masukan sewenang-wenang, tidak hanya objek dalam bahasa. Tapi masalah ini adalah simetris: jika suatu bahasa adalah di P kemudian jadi adalah pelengkap nya. Pertanyaan apakah komplemen dari setiap bahasa NP juga merupakan bahasa NP adalah belum terpecahkan.

(Analogi ini menunjukkan bahwa masalah NP adalah masalah P seperti set ulang adalah set yang dapat dikomputasi. Itu agak benar, tetapi bisa menyesatkan. Ini adalah fakta dasar bahwa set yang kembali dan yang kembali dapat dihitung, sementara tidak diketahui apakah setiap set yang NP dan Co-NP dalam P).