Bisakah ditentukan jika bahasa L terletak di NP?

Diberi bahasa L yang didefinisikan oleh Turing Machine yang memutuskannya, apakah mungkin menentukan secara algoritmik apakah L terletak pada NP?

Tidak. Pertama, oleh Teorema Rice, ini adalah properti dari TM yang hanya bergantung pada bahasa yang mereka hitung, sehingga tidak dapat dihitung.

Tapi, lebih dari itu, diketahui bahwa indeks set (yaitu, himpunan TM yang bahasa komputasi di N P ) adalah Σ 0 3 -Lengkap ( Σ 0 3 di aritmatika hirarki computability, bukan hierarki polinomial).$NP$$NP$$\Sigma^0_3$$\Sigma^0_3$

Pertanyaan seperti ini pertama kali diselidiki oleh Hajek . Untuk lebih lanjut, lihat misalnya artikel ini oleh Ken Regan.

Beberapa nugget hebat dari koran Hajek:

• Kumpulan indeks adalah Σ 0 3 -lengkap.$P$$\Sigma^0_3$
• adalah Π 0 2 -lengkap$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$$\Pi^0_2$
• Ada mesin Turing total (berhenti pada semua input) sedemikian rupa sehingga P L i = N P L i tetapi pernyataan " P L i = N P L i " adalah independen (di mana L i = L ( M i ) ) . Demikian pula untuk relativizations mana P ≠ N P .$M_i$$P^{L_i} = NP^{L_i}$$P^{L_i} = NP^{L_i}$$L_i = L(M_i)$$P \neq NP$

Jawaban untuk pertanyaan literal Anda adalah tidak, seperti yang ditunjukkan Joshua Grochow.

Namun, seperti yang dinyatakan Holger, adalah mungkin untuk memeriksa dalam waktu linier apakah mesin Turing nondeterministic (NTM) "jam itu sendiri" dan berhenti setelah langkah n ^ k untuk beberapa konstanta k, melalui beberapa cara standar mensimulasikan jam (seperti kode di bawah ini). Seringkali ketika sebuah makalah atau buku akan menyarankan (secara tidak benar) bahwa adalah mungkin untuk menentukan apakah suatu NTM adalah waktu polinomial, inilah yang sesungguhnya mereka maksudkan. Mungkin ini sebabnya Anda mengajukan pertanyaan? (Saya memiliki pertanyaan yang sama ketika saya pertama kali mempelajari teori kompleksitas dan di suatu tempat melihat pernyataan bahwa adalah mungkin untuk memeriksa apakah TM adalah pol waktu). Pertanyaan sebenarnya adalah mengapa orang mungkin ingin melakukan ini, yang saya bahas di bawah setelah menjelaskan bagaimana .

Ada banyak cara untuk menambahkan fitur jam seperti itu. Sebagai contoh, bayangkan pada input x panjang n, secara bergantian mengeksekusi satu pernyataan dari "algoritma primer" yang di-clock, dan kemudian satu pernyataan dari algoritma berikut ini, yang diakhiri dengan (sesuatu yang dekat dengan) langkah-langkah n ^ k:

untuk i_1 = 1 ke n
  untuk i_2 = 1 ke n
...
        untuk i_k = 1 ke n
          tanpa op;
kembali;

Jika kode di atas kembali sebelum algoritma utama berhenti, maka hentikan seluruh perhitungan (katakanlah, dengan penolakan).

Algoritma yang memutuskan apakah suatu NTM dalam bentuk ini, jika ditafsirkan sebagai upaya algoritma untuk memutuskan apakah inputnya adalah NTM waktu-poli, akan melaporkan beberapa negatif palsu: beberapa NTM dijamin akan berhenti dalam waktu polinomial, meskipun mereka tidak bergantian menjalankan satu pernyataan dari suatu algoritma dengan satu pernyataan dari jam seperti kode di atas (karenanya akan ditolak meskipun menjadi waktu-poli).

Tetapi tidak ada positif palsu. Jika NTM lulus tes, maka pasti berhenti dalam waktu polinomial, maka itu mendefinisikan beberapa bahasa NP. Namun, mungkin perilaku algoritma primer yang mendasarinya diubah, jika jam kadang-kadang habis sebelum algoritma primer berhenti, menyebabkan perhitungan ditolak meskipun algoritma utama mungkin telah diterima jika diberi waktu yang cukup untuk menyelesaikannya. Oleh karena itu bahasa yang diputuskan mungkin berbeda dari algoritma utama. Tapi, dan ini adalah kunci, jika algoritma utama yang dieksekusi sebenarnya adalah algoritma polinomial-waktu yang berjalan dalam waktu p (n), dan jika konstanta k dalam jam cukup besar sehingga n ^ k> p (n), maka algoritma utama akan selalu berhenti sebelum jam habis. Dalam hal ini, jawaban dari algoritma primer tidak diubah, sehingga algoritma primer dan simulasi clock NTM karenanya memutuskan bahasa NP yang sama.

Mengapa ini penting? Ini berarti bahwa adalah mungkin untuk "menghitung semua bahasa NP" (yang seperti yang saya katakan dalam literatur sering tidak akurat dinyatakan sebagai "memutuskan apakah NTM yang diberikan adalah waktu-poli" atau "menyebutkan semua NTM waktu-poli"). Lebih tepatnya, dimungkinkan untuk menyebutkan daftar tak terbatas M_1 M_2 NTM, ..., dengan properti yang

1. Setiap M_k berjalan dalam waktu polinomial (misalnya, dengan melampirkan jam ^ k-time ke M_k), maka memutuskan beberapa bahasa NP, dan
2. Setiap bahasa NP adalah bahasa yang ditentukan oleh beberapa M_i dalam daftar.

Apa yang tidak terjadi adalah bahwa setiap NTM polinomial-waktu ada dalam daftar. Tetapi setiap bahasa NP memiliki jumlah NTM yang tak terbatas yang mewakilinya. Dengan demikian, setiap bahasa NP dijamin memiliki setidaknya beberapa perwakilan NTM dalam daftar, khususnya semua NTM pada indeks k yang cukup besar yang n ^ k melebihi waktu berjalan M_k.

Ini berguna untuk melakukan trik seperti diagonalisasi, yang membutuhkan penghitungan algoritme yang tidak terbatas (atau tidak terbatas) dari semua bahasa NP. Dan tentu saja, seluruh diskusi ini berlaku untuk banyak jenis mesin selain NTM waktu-poli, seperti TM-waktu deterministik poli-waktu.

Saya ingin berkomentar bahwa jawabannya adalah ya jika Anda menganggap inputnya sebagai mesin Turing yang memiliki jam, yaitu, ada jam yang memungkinkan mesin Turing melakukan $p(n)$langkah-langkah dan kemudian menerima / menolak. Sekarang memeriksa apakah bahasa yang diputuskan oleh mesin dalam NP adalah properti sintaksis yang bermuara untuk memutuskan apakah mesin tersebut adalah mesin Turing nondeterministic yang terbentuk dengan baik dengan jam polinomial.