Apakah batas runtime dalam P dapat dipilih? (jawab: tidak)

Pertanyaan yang diajukan adalah apakah pertanyaan berikut dapat dipilih:

Masalah   Mengingat integer $k$ dan mesin Turing $M$ berjanji untuk berada di P, adalah runtime dari $M$ ${O}(n^k)$ sehubungan dengan panjang input $n$ ?

Jawaban sempit "ya", "tidak", atau "terbuka" dapat diterima (dengan referensi, sketsa bukti, atau tinjauan pengetahuan saat ini), tetapi jawaban yang lebih luas juga sangat disambut baik.

Menjawab

Emanuele Viola telah memposting bukti bahwa pertanyaan itu tidak dapat diputuskan (lihat di bawah).

Latar Belakang

Bagi saya, pertanyaan ini muncul secara alami dalam mem-parsing jawaban Luca Tevisan untuk pertanyaan. Apakah runtime untuk P memerlukan sumber daya EXP ke batas atas? ... Apakah contoh nyata diketahui?

Pertanyaannya juga berkaitan dengan pertanyaan MathOverflow: Apa masalah paling menarik yang belum diputuskan Turing dalam matematika? , dalam variasi di mana kata "matematika" diubah menjadi "teknik," dalam pengakuan bahwa estimasi runtime adalah masalah rekayasa di mana-mana yang terkait dengan (misalnya) teori kontrol dan desain sirkuit.

Dengan demikian, tujuan luas dalam mengajukan pertanyaan ini adalah untuk mendapatkan apresiasi / intuisi yang lebih baik mengenai aspek praktis estimasi runtime di kelas kompleksitas P yang layak (yaitu, membutuhkan sumber daya komputasi dalam P untuk memperkirakan), dibandingkan tidak layak (yaitu, membutuhkan sumber daya komputasi dalam EXP untuk memperkirakan), dibandingkan secara formal tidak dapat diputuskan.

--- edit (post-answer) ---

Saya telah menambahkan teorema Viola ke wiki komunitas MathOverflow, "Masalah Menarik-Turing yang tidak dapat diputuskan". Kontribusi pertama wiki terkait dengan kompleksitas kelas P; ini membuktikan kebaruan, kealamian, dan ruang lingkup luas teorema Viola (dan IMHO keindahannya juga).

--- edit (post-answer) ---

Monograf Juris Hartmanis ' Perhitungan layak dan properti kompleksitas yang dapat dibuktikan (1978) mencakup banyak materi yang sama dengan bukti Emanuele Viola.

Masalahnya tidak dapat ditentukan. Secara khusus, Anda dapat mengurangi masalah penghentian sebagai berikut. Mengingat sebuah contoh dari masalah terputus-putus, membangun sebuah mesin baru M ' yang bekerja sebagai berikut: masukan panjang n , mensimulasikan M pada x untuk n langkah. Jika M menerima, loop untuk n 2 langkah dan berhenti; jika tidak loop untuk n 3 langkah dan berhenti.$(M,x)$$M'$$n$$M$$x$$n$$M$$n^2$$n^3$

Jika berhenti pada x ia melakukannya dalam t = O ( 1 ) langkah-langkah, jadi waktu menjalankan M ′ akan menjadi O ( n 2 ) . Jika M tidak pernah berhenti maka jangka waktu M ′ setidaknya n 3 .$M$$x$$t=O(1)$$M'$$O(n^2)$$M$$M'$$n^3$

Karenanya Anda dapat memutuskan apakah menerima x dengan memutuskan apakah jangka waktu M ′ adalah O ( n 2 ) atau O ( n 3 ) .$M$$x$$M'$$O(n^2)$$O(n^3)$

Ini adalah pengulangan dari jawaban Emanuele Viola dengan tujuan agar lebih dimengerti.

Kami menunjukkan bahwa masalah yang diberikan tidak dapat ditentukan dengan mengurangi masalah umum H yang terputus padanya.$P$$H$

$(M, x)$$M(x)\downarrow$$M$$x$$M^*$

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Sekarang kami mengamati implikasi berikut:

$\begin{align*} M(x) \downarrow \quad &\Rightarrow \exists n_0 \in \mathbb{N} : M \text{ halts on } x \text{ after at most } n_0 \text{ steps} \\ &\Rightarrow \forall y : n \geq n_0 \Rightarrow M^*(y) \text{ executes } n^2 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \mathcal{O}(n^2) \end{align*}$

dan

$\begin{align*} M(x) \uparrow \quad &\Rightarrow \forall n \in \mathbb{N} : M \text{ does not halt on } x \text{ in less than } n \text{ steps} \\ &\Rightarrow \forall y : M^*(y) \text{ executes } n^3 \text{ arbitrary steps} \\ &\Rightarrow T_{M^*}(n) \in \Omega(n^3) \end{align*}$

$H(M,x) \Leftrightarrow P(M^*,2)$$P$$H$$\square$

$n \mapsto C \cdot n + D$$C, D \in \mathbb{N}$

$Cn+D$

Masalahnya juga dipecahkan dalam artikel saya " Isi intens Teorema Rice " POPL'2008, di mana saya membuktikan bahwa tidak ada "klik kompleksitas" yang dapat ditentukan. Klik kompleksitas adalah kelas program tertutup, dengan perilaku dan kompleksitas yang sama. Saya juga menyediakan kondisi yang diperlukan untuk properti semi-decidable.

Program yang berjalan di O (n ^ k) adalah klik kompleksitas dalam arti di atas, maka himpunan tidak dapat ditentukan.

Hasilnya juga baru-baru ini diperluas ke pengaturan subkursif (seperti P) oleh Mathieu Hoyrup: Properti decidable dari fungsi subkursif (ICALP 2016).

$Σ^0_2$

$Σ^0_2$$S$$S$$O(n^2)$$Σ^0_2$$S$

$Σ^0_2$$φ$$φ(x) ⇔ ∃k ∀m \, ψ(x,k,m)$$ψ$

$φ(x)$$O(n^2)$$n$

$k$$n$
$∀m<n \, ψ(x,k,m)$

$n^2$

$c$$≤n^2+c$$Π^0_1$$Σ^0_2$

Berikut ini adalah analisis / sudut / hasil / analisis baru yang lebih sistematis terhadap pertanyaan ini & yang terkait, memperkenalkan konsep "verifikasi algoritmik" dan analog Beras-seperti-thm untuk teori kompleksitas. satu bagian yang relevan dari abstrak adalah sebagai berikut dan ada banyak teorema terkait lainnya yang berkaitan dengan provabilitas P vs NP dll

• Mengapa Konsep Kompleksitas Komputasi Sulit untuk Matematika / Hromkovic yang Dapat Diverifikasi

  Pertama, kami membuktikan teorema Rice untuk tidak dapat dibuktikan, mengklaim bahwa setiap masalah semantik nontrivial tentang program hampir tidak ada di mana-mana yang dapat dipecahkan dalam algoritma "AV" yang dapat diverifikasi secara Algorithmically. Dengan menggunakan ini, kami menunjukkan bahwa ada banyak tak terbatas algoritma (program yang terbukti algoritma) yang tidak ada bukti bahwa mereka bekerja dalam waktu polinomial atau bahwa mereka tidak bekerja dalam waktu polinomial. ...

  Perhatikan bahwa, jika P! = NP dapat dibuktikan dalam AV-matematika, maka untuk setiap algoritma A dapat dibuktikan bahwa "A tidak menyelesaikan KEPUASAN atau A tidak bekerja dalam waktu polinomial". Menariknya, kami akhirnya menunjukkan bahwa ada algoritma yang tidak dapat dibuktikan bahwa mereka tidak bekerja dalam waktu polinomial, atau bahwa mereka tidak menyelesaikan KEPUASAN. Selain itu, ada suatu algoritma penyelesaian KEPUASAN yang tidak dapat dibuktikan dalam AV-matematika bahwa itu tidak bekerja dalam waktu polinomial.

  Selanjutnya, kami menunjukkan bahwa P = NP menyiratkan adanya algoritma X yang klaim "X memecahkan KEPUASAN dalam waktu polinomial" tidak dapat dibuktikan dalam AV-matematika.

Solusi dari Viola dapat digeneralisasi ke waktu berjalan (di luar poli): Anda dapat mengurangi masalah terputusnya sebagai berikut. Diberikan contoh (M, x) dari masalah terputus-putus, buatlah sebuah mesin baru M ′ yang bekerja sebagai berikut: pada input panjang n, ia mensimulasikan M pada x untuk langkah-langkah f (n) atau sampai M berhenti, di mana f (n ) adalah fungsi peningkatan sembarang (lebih besar dari konstan) dari n. (Obs .: M ′ membaca input secara bertahap, untuk menghindari pemborosan waktu linear [O (n)] hanya untuk membaca semua input yang tidak perlu, jika cukup besar dan M berhenti.)

Jika M berhenti pada x ia melakukannya dalam T = O (1) langkah-langkah, sehingga jangka waktu M ′ akan menjadi O (1). Jika M tidak pernah berhenti maka waktu menjalankan M ′ adalah O (n ^ 2 * f (n)).

Karenanya Anda dapat memutuskan apakah M menerima x dengan memutuskan apakah jangka waktu M ′ adalah O (1) atau O (n ^ 2 * f (n)).

Kemudian, kode bantu dari Raphael dapat digeneralisasi sesuai dengan:

Misalkan (M, x) adalah setiap instance dari Masalah Pemutusan, yaitu kita harus memutuskan apakah M berhenti pada x. Buat Mesin Turing deterministik (DTM) M * yang berfungsi sebagai berikut:

1. M * (input) = {
2. n: = 0
3. Baca simbol pertama dari input
4. Loop:
5. n: = n +1
6. Simulasikan M (x) untuk langkah f (n) atau hingga M (x) berhenti
7. Baca simbol selanjutnya dari input
8. Ulangi hingga end_of_input atau hingga M (x) berhenti
9. }

Sekarang kami mengamati implikasi berikut:

M berhenti pada x setelah paling banyak k (konstan) langkah => T (M *) = O (1) dan

M tidak pernah berhenti pada x => T (M *) = O (n ^ 2 * f (n))

Oleh karena itu, bahkan memutuskan apakah waktu berjalan DTM sewenang-wenang lebih besar daripada konstan sama sulitnya dengan Menghentikan Masalah. □