Apakah P berisi bahasa yang keberadaannya tidak tergantung pada PA atau ZFC? (Wiki komunitas TCS)

Jawab: tidak dikenal.

Pertanyaan yang diajukan wajar, terbuka, dan tampaknya sulit; pertanyaannya sekarang adalah wiki komunitas.

Gambaran

Pertanyaannya adalah mencoba untuk membagi bahasa yang termasuk dalam kelas kompleksitas  - bersama dengan mesin Turing keputusan (TMs) yang menerima bahasa ini - menjadi dua subkelas pelengkap:$P$

• bahasa gnostik dan TM (yang layak untuk divalidasi / dipahami), dibandingkan
• bahasa dan TM samar (yang tidak layak untuk memvalidasi / mengerti).

Definisi: angka gnostik vs cryptic , TM, dan bahasa

Dalam kerangka kerja aksioma PA dan ZFC , kami membedakan gnostik dari mesin dan bahasa Turing samar sebagai berikut:

D0   Kami mengatakan bahwa bilangan real yang dapat dihitung   adalah gnostik jika dikaitkan dengan set TM yang tidak kosong, dengan masing-masing TM ditentukan dalam PA sebagai daftar eksplisit angka yang terdiri dari kode yang valid pada TM universal, sehingga untuk akurasi apa pun ϵ > 0 diberikan sebagai input, setiap TM yang dibuktikan (dalam ZFC) berhenti dengan jumlah output o yang terbukti (dalam ZFC) memenuhi r - ϵ < o < r + ϵ .$r$$\epsilon\gt0$$o$$r-\epsilon\lt o\lt r+\epsilon$

Keterangan   Diketahui bahwa beberapa real yang dihitung tidak gnostik (untuk contoh konkret lihat jawaban Raphael Reitzig untuk pertanyaan jkff " Apakah ada bukti keberadaan algoritma yang tidak konstruktif? "). Untuk menghindari bergulat dengan angka-angka ini-belum-canggung, pembatasan diberlakukan bahwa eksponen runtime dapat dihitung oleh TM yang secara eksplisit disebutkan dalam PA (sebagai kontras dengan TM yang secara implisit ditentukan dalam ZFC). Untuk diskusi lebih lanjut, lihat bagian Pertimbangan Definisi (di bawah).

Sekarang kita mencari definisi yang menangkap intuisi bahwa kelas kompleksitas mencakup subset dari bahasa samar yang tidak dapat ditugaskan ditugaskan oleh eksponen runtime (gnostik) batas bawah. $P$

Untuk melihat ke depan, definisi penutup ( D5 ) menentukan ide keputusan kanonik cryptic TM , yang definisinya dibuat dengan maksud untuk meniadakan pengurangan yang (secara sepele) menutupi perhitungan cryptic dengan menutupi komputasi epi-komputasi yang berlebihan. Dasar pemikiran dan sumber-sumber definisi utama ini dibahas kemudian - di bawah judul Pertimbangan Definisi  - dan kontribusi komentar oleh Timothy Chow, Peter Shor, Sasho Nikolov, dan Luca Trevisan dengan penuh syukur diakui.

D1   Diberikan mesin Turing M yang berhenti untuk semua string input, M disebut cryptic iff pernyataan berikut ini tidak dapat dibuktikan atau disangkal untuk setidaknya satu bilangan real gnostik  :$r \ge 0$

Pernyataan: runtime M adalah sehubungan dengan panjang input ${O}(n^r)$$n$

Mesin Turing yang tidak samar kami katakan adalah TM gnostik.

D2   Kami mengatakan bahwa keputusan mesin Turing M efisien jika ia memiliki runtime eksponen gnostik  sehingga bahasa L yang diterima M tidak diterima oleh TM lain yang memiliki eksponen runtime gnostik lebih kecil dari  r .$r$$r$

D3   Kami mengatakan bahwa bahasa L adalah cryptic jika diterima oleh (a)  setidaknya satu mesin Turing M adalah yang efisien dan samar, dan terlebih lagi (b)  tidak ada TM yang efisien dan gnostik yang terbukti menerima L.

Untuk mengekspresikan D3 dengan cara lain, suatu bahasa adalah cryptic iff TMs yang menerima bahasa itu paling efisien adalah cryptic itu sendiri.

Bahasa yang tidak samar, kami katakan adalah bahasa gnostik .

D4   Kami mengatakan bahwa TM cryptic sangat samar jika bahasa yang diterima adalah cryptic.

D5   Kami mengatakan bahwa TM yang sangat cryptic adalah kanonik cryptic jika efisien.

Untuk mengekspresikan D5 dengan cara lain, setiap bahasa cryptic diterima oleh serangkaian TM keputusan cryptic kanonik, yang merupakan keputusan TM paling efisien yang menerima bahasa itu.

Pertanyaan yang diajukan

Dugaan berikut C0 adalah alami dan (tampaknya) terbuka:

C0   Kompleksitas kelas P mengandung setidaknya satu bahasa samar.

Tiga pertanyaan diajukan, Q1 - Q3 , yang pertama adalah:

Q1   Apakah dugaan C0 tidak tergantung pada PA atau ZFC?

Dengan asumsi itu C0 benar - baik dibuktikan dalam ZFC, atau sebagai aksioma independen yang merupakan tambahan untuk ZFC - dua pertanyaan lebih lanjut adalah alami:

Q2   Dapatkah setidaknya satu bahasa cryptic dalam P disajikan secara konkret, yaitu, dipamerkan sebagai kamus kata-kata eksplisit dalam alfabet terbatas yang mencakup semua kata hingga panjang tertentu? Jika demikian, perlihatkan kamus seperti itu.

Q3   Dapatkah setidaknya satu keputusan kanonik cryptic TM disajikan secara konkret, yaitu, sebagai deskripsi yang memungkinkan untuk membangun mesin Turing fisik yang memutuskan (dalam waktu polinomial) semua kata-kata kamus Q2 ? Jika demikian, buat mesin Turing seperti itu dan dengan komputasi dengannya, tunjukkan kamus bahasa samar Q2 .

Pertimbangan definisi

Definisi D0 menyiratkan bahwa setiap bilangan real gnostik dapat dihitung, tetapi diketahui bahwa beberapa bilangan real yang dapat dihitung tidak gnostik. Sebagai contoh, lihat jawaban pada MathOverflow oleh Michaël Cadilhac dan Ryan Williams dan pada TCS StackExchange oleh Raphael Reitzig . Secara lebih umum, definisi D0 – D5 dibuat untuk mengecualikan referensi ke eksponen runtime non-gnostik.

Sebagaimana dibahas dalam wiki TCS " Apakah P berisi bahasa yang tidak dapat dipahami? ", Definisi D0-D5 memastikan bahwa setiap bahasa rahasia diterima oleh setidaknya satu TM yang kanonik kriptik. (Perhatikan juga bahwa dalam pertanyaan ini, kata "cryptic" menggantikan kata yang kurang deskriptif "tidak dapat dipahami" yang digunakan dalam wiki).

Selain itu - mengingat D3 (a) dan D3 (b)  - tidak ada reduksi komputasional dari TM kriptonik yang kanonik menjadi TM gnostik yang terbukti mengenali bahasa yang sama. Secara khusus, D3 (a) dan D3 (b) menghalangi strategi reduksi polimiter yang diuraikan dalam komentar oleh Peter Shor , dan oleh Sasho Nikolov , dan secara independen oleh Luca Trevisan , dan menghalangi juga strategi reduksi yang dicatat secara polinomi dari Timothy Chow , semuanya yang juga menutupi komputasi cryptic dengan cara overlay komputasi epi-komputasi yang berlebihan .

Secara umum, definisi "gnostik" dan "samar" sengaja disetel agar kuat sehubungan dengan pengurangan matematis sepele (dan sangat mungkin bahwa penyempurnaan lebih lanjut dari definisi ini mungkin diinginkan).

Pertimbangan metodologis

Ulasan Lance Fortnow " Status masalah P versus NP " mensurvei metode untuk membangun kemandirian (atau sebaliknya) dugaan dalam teori kompleksitas; terutama yang diinginkan adalah saran tentang bagaimana metode yang ulasan Lance dapat membantu (atau tidak) untuk menjawab Q1 .

Jelas bahwa banyak pertanyaan lebih lanjut adalah wajar. Misalnya, dugaan Hartmanis-Stearns mengilhami kita untuk bertanya, "Apakah mesin Turing multitape real-time samar ada? Apakah keberadaan mereka (atau tidak) tidak tergantung pada PA atau ZFC?"

Pertimbangan tipe Zeilberger

Jika Q1 dijawab oleh "ya", maka nubuat yang memutuskan keanggotaan dalam $P$ ada di luar PA atau ZFC, dan karena itu, elemen penting dari teori kompleksitas modern (saat ini) tidak diketahui berada dalam sistem formal apa pun. logika.

Dalam hal ini teori kompleksitas berbeda dari sebagian besar disiplin ilmu matematika, sedemikian rupa sehingga kekhawatiran yang diungkapkan oleh Doron Zeilberger dalam " Opini 125: Sekarang Alan Turing yang berusia 100 tahun, sekarang saatnya untuk memiliki Pandangan Baru pada Kontribusi Seminalnya." , Itu melakukan banyak kebaikan tetapi juga banyak bahaya "bisa dibilang beralasan.

Kekhawatiran Zeilberger mengambil bentuk eksplisit sebagai kriteria Z0    (! Q1  ) && (! C0  ), yang setara dengan kriteria berikut:$\equiv$

Z0:   Kriteria sensibilitas Zeilberger   Definisi kompleksitas kelas P   disebut Zeilberger-masuk akal jika semua bahasa di P terbukti gnostik.

Saat ini tidak diketahui apakah definisi Stephen Cook tentang kelas kompleksitas P   adalah Zeilberger-masuk akal.

Pertimbangan motivasi

Definisi "gnostik" dan "samar" dibuat dengan pandangan ke arah (akhirnya) menentukan dugaan seperti berikut:

C1   Misalkan dan N P ′ menjadi batasan gnostik P dan N P resp. Maka P ′ ≠ N P ′ dapat dibuktikan atau disangkal dalam PA atau ZFC.$P'$$NP'$$P$$NP$$P' \ne NP'$

C2   (seperti yang secara eksplisit dibuktikan dalam PA atau ZFC)$P' \ne NP'$

Jelas C2   C1 , dan sebaliknya dapat dibuktikan bahwa bukti teorema (meta) C1 dapat memberikan panduan menuju bukti teorema C2 (yang lebih kuat) .$\to$ 

Motivasi keseluruhan adalah harapan / intuisi / harapan bahwa untuk beberapa perbedaan yang diselaraskan antara TM dan bahasa gnostik dan samar, bukti C1 dan mungkin bahkan C2 dapat menerangi - dan bahkan memiliki implikasi praktis yang sebanding dengan - mungkin agak lebih sulit dan lebih dalam bukti bahwa . $P\ne NP$

Juris Hartmanis adalah di antara para ahli teori kompleksitas pertama yang secara serius mengejar jalur investigasi ini; lihat monografi Hartmanis ' Komputasi Layak dan Properti Kompleksitas Terbukti (1978), misalnya.

Pertimbangan nomenklatur

Dari Kamus Bahasa Inggris Oxford (OED) kami memiliki:

• gnostic (kata sifat)  Berkaitan dengan pengetahuan; kognitif; intelektual   "Mereka [jumlahnya] ada secara vital, gnostik, dan spekulatif, tetapi tidak secara operatif."

• cryptic (adj)  Tidak segera dimengerti; misterius, penuh teka-teki,   "Alih-alih Aturan sederhana yang bermanfaat bagi umat manusia, mereka [para filsuf] menodai Cruptick dan Kalimat gelap."

Rupanya tidak ada Tinjauan Matematika sebelumnya menggunakan kata "gnostik" dalam arti apa pun. Namun, perhatian tertarik pada artikel terbaru Marcus Kracht " Gnosis " ( Journal of Philosophical Logic , MR2802332), yang menggunakan pengertian OED.

Rupanya tidak ada Tinjauan Matematis yang menggunakan kata "samar" - dalam arti teknis - berkaitan dengan teori kompleksitas. Namun, perhatian tertarik pada artikel Charles H. Bennett " Kedalaman Logika dan Kompleksitas Fisik " (dalam The Universal Turing Machine: A Half-Century Survey , 1988) yang berisi perikop ini.

Jenis kompleksitas lain yang terkait dengan suatu objek adalah kesulitannya, mengingat objek tersebut, untuk menemukan hipotesis yang masuk akal untuk menjelaskannya. Objek yang memiliki kompleksitas semacam ini bisa disebut "samar" : untuk menemukan asal yang masuk akal untuk objek itu seperti memecahkan kriptogram.

Pertimbangan akan kealamian, keterbukaan, dan kesulitan

Kealamian dari pertanyaan-pertanyaan ini menggambarkan tesis monograf Juris Hartmanis ' Kelayakan Komputasi dan Properti Kompleksitas yang Dapat Dibuktikan (1978) bahwa:

"Hasil tentang kompleksitas algoritma berubah sangat radikal jika kita hanya mempertimbangkan sifat-sifat komputasi yang dapat dibuktikan secara formal."

Keterbukaan dan kesulitan dari pertanyaan-pertanyaan ini secara luas sejalan dengan kesimpulan ulasan Lance Fortnow " Status Masalah P vs. NP " (2009) bahwa:

"Tidak ada di antara kita yang benar-benar memahami masalah P versus NP, kita baru mulai mengupas lapisan di sekitar pertanyaan yang semakin kompleks ini."

Panduan wiki

Yang paling dicari adalah penyesuaian definisi dan strategi pembuktian yang secara khusus berkaitan dengan pertanyaan Q1-Q3 dan secara luas menerangkan dugaan tipe-Hartmanis C1-C2 .

Saya pikir ada kesulitan mendasar mendasar dengan pertanyaan yang Anda ajukan di sini (dan Anda bertanya dalam pertanyaan terkait tentang bahasa yang tidak bisa dipahami).

Secara kasar, sepertinya Anda mencari bahasa sedemikian rupa$L$

tapi ZFC tidak tahu bahwa L ∈ P .$L\in P$$L\in P$

Untuk memahami kesulitan dengan pertanyaan Anda, saya pikir Anda harus terlebih dahulu menghargai bahwa ada perbedaan mendasar antara intensional dan ekstensional definisi dari bahasa . Extensionally, L ditentukan oleh apa kata-kata atau bukan anggota L . Artinya, dua bahasa L dan L ' adalah extensionally sama jika dan hanya jika mereka mengandung persis kata-kata yang sama sebagai anggota. Sebaliknya, sebuah intensional definisi L menjelaskan beberapa kondisi untuk sebuah kata untuk berada di L . Mesin Turing yang menerima $L$$L$$L$$L$$L'$$L$$L$$L$, Atau orde pertama Formula yang berlaku jika dan hanya jika x ∈ L , dapat dianggap sebagai definisi intensional dari L .$\phi(x)$$x\in L$$L$

Intinya adalah bahwa setiap yang (ekstensi) dalam P mengakui deskripsi yang sangat mudah, karena P adalah kelas kompleksitas yang disebut "sintaksis". Yaitu, hanya mengambil mesin Turing polinomial clock , yang berakhir tepat pada jumlah waktu yang diinginkan. Setiap sistem yang "masuk akal" untuk melakukan matematika, seperti PA atau ZFC, akan dapat membuktikan bahwa L ∈ P jika Anda menggunakan deskripsi langsung dari L ini .$L$$P$$P$$L\in P$$L$

Jadi jika Anda ingin membingungkan ZFC, Anda harus membuat deskripsi (intensional) yang "terlalu rumit" untuk dikenali ZFC sebagai setara dengan deskripsi L yang sederhana . Ini mungkin, tetapi dalam beberapa hal terlalu mudah untuk menarik. Yang harus Anda lakukan adalah mengambil sesuatu yang kita tahu bahwa ZFC tidak mengerti (misalnya, konsistensi sendiri) dan mencampurnya dengan definisi L entah bagaimana. Sebagai contoh, berikut ini adalah deskripsi satu set bilangan bulat:$L$$L$$L$

adalah genap dan x tidak menyandikan bukti bahwa ZFC tidak konsisten.$x$$x$

Dengan asumsi ZFC konsisten, rumus di atas mendefinisikan himpunan bilangan bulat genap, tetapi ZFC tidak mengetahuinya. Dengan sedikit lebih bermain-main, kita dapat dengan mudah mendapatkan deskripsi dari himpunan bilangan bulat bahkan yang ZFC tidak akan mampu membuktikan di .$P$

Hasilnya adalah jika Anda berharap bahwa alasannya sulit untuk membuktikan bahwa adalah bahwa ada bahasa dalam P yang "terlalu rumit" untuk kita pikirkan, maka saya pikir Anda salah pohon. Secara ekstensi, setiap bahasa dalam P adalah dalam P karena alasan sepele. Anda dapat memperkeruh perairan dengan bermain-main dengan deskripsi bahasa yang tidak jelas dalam bahasa P , tetapi ini adalah trik umum yang tidak ada hubungannya dengan P khususnya, jadi saya tidak berpikir itu menghasilkan banyak wawasan.$P\ne NP$$P$$P$$P$$P$$P$

Q1: $\:$Tidak
Q2:$\:$ Ya, setidaknya dua-1-dalam-biner

Kata pengantar singkat: $\:$ Setiap TM dengan eksponen runtime yang dapat dihitung yang setidaknya 1 adalah transendental.

Bukti:
Biarkan A dan B menjadi set yang tidak terpisahkan secara rekursif .$\:$$M_0$$\:$$M_1$$\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$M_0$$M_1$$r_m$$\:m\in A\:$ maka pernyataan D1 benar] dan [jika $\:m\in B\:$ maka pernyataan D1 salah]. $\;\;$$\langle r_0,r_1,r_2,r_3,...\rangle$$r_m$ yang tidak dapat dibuktikan atau disangkal.$\:$ Karena itu mesin Turing bersifat transendental.


Definisi:
setidaknya-dua-1-dalam-biner adalah himpunan bilangan bulat non-negatif yang
representasi binernya memiliki setidaknya dua 1s.$\:$ (yakin Anda tidak akan pernah menebak ^ _ ^)

Definisi:
M adalah mesin Turing yang memindai representasi biner dari
inputnya, menerima jika ia menemukan setidaknya dua 1s, dan menolak sebaliknya.

Jelas, M memutuskan setidaknya-dua-1-dalam-biner dan memiliki eksponen runtime 1, dan tidak ada mesin Turing lain dengan eksponen runtime yang lebih kecil juga memutuskan setidaknya-dua-1-dalam-biner.
Sepele,$\: 1\leq 1 \:$$1$$\;\;$Oleh Lemma, M efisien dan transendental.
Ini berarti setidaknya-dua-1-dalam-biner juga transendental.

Oleh karena itu TPCCC adalah teorema PA (dan ZFC), dan
paling tidak dua-1-dalam-biner adalah bahasa transendental konkret.

$x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$$n$$x_n$$x_n$$x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$

$x$$\bf{ZF}$

Definisi 2: Untuk setiap gnostik nyata $x > 1$biarkan $M'_x$ menjadi mesin Turing yang mengambil indeks $n$ dari mesin Turing $N$ dan input $s$, mensimulasikan $N$ di $s$ untuk $|s|^x/\log(|s|)$ langkah-langkah (fungsi ini konstruktif waktu, karena $x$adalah gnostik), dan membalikkan hasilnya. Dengan Teorema Rekursi, kita dapat memilih$M_x$ menjadi $M'_x$ dengan indeks tetap $M_x$sebagai input pertama. Kemudian argumen standar (Teorema Hierarki Waktu) menunjukkan hal itu$M_x$ memiliki runtime $\mathcal O(|s|^y)$ kapan tepatnya $y\ge x$, and that $M_x$ is efficient for its language.

Therefore, for $x$ as in Definition 1, $M_x$ will run in time $\mathcal O(|s|^2)$ precisely if $x = 2$, ie if $\bf{ZF}$ is consistent; moreover this fact will itself be provable in $\bf ZF$. So [if $\bf ZF$ is consistent], $M_x$ is a [strongly and canonically] cryptic machine, and this fact will be provable in $\bf ZF + Con(\bf ZF)$.

However, $\bf ZF + \not Con(\bf ZF)$ proves that all languages in $\bf P$ are gnostic, since it proves that $\bf ZF$ proves that every language has runtime $\mathcal O(|s|^z)$ for every $z$. So it is undecidable in $\bf ZF$ whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for $M_x$ is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.