Apakah P mengandung bahasa yang tidak bisa dipahami? (Wiki komunitas TCS)

Jawab: tidak dikenal

Terima kasih banyak untuk semua yang membantu memperbaiki pertanyaan ini dan definisi yang terkait dengannya.

Definisi wiki ini memberikan titik awal untuk wiki TCS yang lebih baru " Apakah P berisi bahasa yang keberadaannya tidak bergantung pada PA atau ZFC? (Wiki komunitas TCS) ".

Wiki yang lebih baru lebih disukai karena definisi dan nomenklaturnya secara substansial lebih canggih daripada wiki yang lebih tua ini.

Secara khusus, wiki ini lebih tua nomenklatur dimengerti $\Leftrightarrow$ dipahami bahasa dan TM yang digantikan di wiki baru dengan samar gnostik . Selain rincian definisi - yang penting - kedua wiki membahas kelas pertanyaan yang serupa. $\Leftrightarrow$

Jawaban lebih lanjut dipersilakan

Jawaban lebih lanjut dipersilahkan (tidak perlu dikatakan), dan kemungkinan penyetelan definisi lebih lanjut sesuai. Satu pelajaran utama adalah bahwa kelas pertanyaan ini menantang untuk dirumuskan dan masih lebih menantang untuk dijawab dengan ketat.

Sebagai latar belakang, jawaban Sasho Nikolov dinilai "diterima," karena memberikan rumusan yang menangkap maksud pertanyaan: jawaban atas pertanyaan itu (tampaknya) tidak diketahui.

Jawaban berharga Philip White memotivasi definisi bertingkat dari TM yang tidak dapat dipahami, versus sangat tidak bisa dipahami, versus secara kanonik tidak dapat dipahami (per daftar "definisi definisi tidak dapat dimengerti" di bawah).

Pernyataan pertanyaan berikut untuk sementara memasukkan wawasan dan saran berharga yang diberikan oleh Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer, Peter Shor, dan juga posting weblog berharga oleh Luca Trevisan .

Definisi formal

Mesin Turing yang tidak dapat dipahami didefinisikan (dalam ZFC) sebagai berikut:

D1 Diberikan mesin Turing M yang terbukti berhenti untuk semua string input, M disebut tidak dapat dipahami jika pernyataan berikut ini tidak dapat dibuktikan atau disangkal untuk setidaknya satu bilangan real semidefinite positif : $r$

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

Sebaliknya, M disebut dapat dipahami jika tidak dapat dipahami.

Disambiguasi decidable

Entri Wikipedia " Masalah yang tidak dapat diputuskan: Contoh-contoh pernyataan yang tidak dapat dipastikan " secara ringkas mengulas perbedaan pengertian dari istilah "tidak dapat dipastikan" yang lazim dalam literatur bukti-teoretis versus komputabilitas-teoretis. Dengan tujuan untuk menghindari ambiguitas, definisi dan pertanyaan yang diajukan hanya menggunakan terminologi "tidak dapat dibuktikan atau disangkal."

Referensi lebih lanjut dalam hal ini adalah catatan mata kuliah Jeremy Avigad " Ketidaklengkapan melalui Masalah yang Terputus ", esai weblog Scott Aaronson " Teorema Rosser melalui mesin Turing " dan posting weblog Luca Trevisan Dua pertanyaan menarik .

Tentang keberadaan mesin Turing yang tidak bisa dipahami

Mesin-mesin Turing yang tidak dapat dipahami itu ada mengikuti secara konkret dari sebuah konstruksi oleh Emmanuele Viola dan secara luas dari kerangka kompleksitas-teoretis Juris Hartmanis. Secara khusus, konstruksi Viola menyediakan, melalui metode catatan kursus Jeremy Avigad (seperti yang saya mengerti), lemma berikut:

Lemma [Implikasi Viola]
(jika bahasa L diterima oleh TM yang dapat dipahami) (L diterima oleh TM yang tidak dapat dipahami). $\to$

Menghargai naturalitas dalam mendefinisikan ketidakmampuan memahami

Wajar untuk bertanya-tanya apakah implikasi sebaliknya terhadap Implikasi Viola benar.

Pertimbangan naturalitas mensyaratkan bahwa implikasi sebaliknya harus diajukan dengan hati-hati, dalam komentar Philip White di bawah ini menunjukkan bagaimana untuk secara sepele mengurangi TM yang tidak dapat dipahami menjadi TM yang dapat dipahami melalui polylimiter , yang merupakan modul komputasi yang (pada dasarnya) "pad" runtime dari mesin yang tidak dapat dimengerti sehingga untuk menguranginya menjadi mesin yang komprehensif.

Secara khusus, adalah wajar untuk meminta kita untuk “secara tidak estetika menutupi elemen-elemen lama yang tidak dapat dipahami dengan memperkenalkan elemen-elemen baru yang tidak dapat dipahami .” Tantangan utama yang terkait dengan pertanyaan yang diajukan berjumlah "Apakah ada definisi alami tentang tidak dapat dipahami?" ... yang (mengingat diskusi di sini tentang TCS), kita mungkin harus menganggapnya sebagai meta-pertanyaan nontrivial yang mungkin memiliki lebih dari satu jawaban alami.

Dengan pandangan pada prinsip naturalitas panduan ini, definisi bertingkat dari ketidaktahuan ditentukan sebagai berikut.

Definisi yang dinilai tidak dapat dipahami

D2 Kami mengatakan bahwa Turing mesin M adalah efisien IFF memiliki runtime eksponen sehingga L bahasa yang M menerima diterima oleh ada TM lain yang memiliki runtime eksponen lebih kecil dari . $r$ $r$

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

D4 Kami mengatakan bahwa TM yang tidak dapat dipahami sangat tidak dapat dipahami jika bahasa yang diterimanya tidak dapat dipahami.

D5 Kami mengatakan bahwa TM yang sangat tidak dapat dipahami secara kanonik tidak dapat dipahami jika efisien.

Definisi-definisi ini memastikan bahwa setiap bahasa yang tidak dapat dipahami diterima oleh setidaknya satu TM yang secara kanonik tidak dapat dipahami, dan terlebih lagi - dalam pandangan D3 (a) dan D3 (b) - tidak ada pengurangan polimiter sepele dari TM yang secara kanonik tidak dapat dipahami menjadi TM yang dapat dipahami. yang terbukti mengakui bahasa yang sama.

Tiga pertanyaan itu diajukan

P1 Apakah kelas kompleksitas P mengandung bahasa yang tidak dapat dipahami?

Q2 Dapatkah setidaknya satu bahasa yang tidak dapat dipahami diwakili secara konkret? (jika demikian, berikan contoh konstruktif).

Q3 Dapatkah setidaknya satu TM yang secara kanonik tidak dapat dipahami diwakili secara konkret? (jika demikian, berikan contoh konstruktif).

Motivasi

Sifat dimengerti dari kelas kompleksitas P menghalangi pemahaman kelas luas masalah yang (untuk pengusul asli pertanyaan ini ) termasuk Terry Tao biru-Eyed Kepulauan Teka-teki , Dick Lipton dan Ken Regan Mm-Choice permainan , dan hibridisasi mereka di konteks Newcomb's Paradox melalui Balanced Advantage Newcomb Game .

Seperti yang dikatakan oleh monograf Juris Hartmanis ' Kelayakan dan sifat kompleksitas yang dapat dibuktikan (1978):

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

Perjuangan untuk membangun definisi dan postulat yang diposisikan baik yang menangkap wawasan Hartmanis membantu kita untuk lebih menghargai bahwa kelas kompleksitas P memiliki beberapa bahasa yang sangat aneh di dalamnya, yang diakui oleh mesin Turing yang sangat aneh, yang sifatnya kami (saat ini sifatnya) ) sangat jauh dari genggaman. Sangat mengejutkan bahwa dalam pengertian yang sangat teliti, saat ini tidak diketahui apakah kelas kompleksitas P dapat dipahami.

Terima kasih banyak diberikan kepada semua yang telah berkontribusi komentar dan jawaban.

cc.complexity-theory complexity-classes turing-machines decidability John Sidles
sumber

Tolong jelaskan istilah "(mesin Turing) dinyatakan dalam P."

Tsuyoshi Ito

Dalam masalah yang dinyatakan dalam definisi "tidak bisa dipahami dalam P," apa sebenarnya input? Apakah mesin Turing bagian dari input atau diperbaiki? Selain itu, bagaimana bilangan real ditentukan sebagai string?

Tsuyoshi Ito

r

$r$

M

$M$

Seperti yang dijelaskan Sasho sebelumnya, masalah yang dinyatakan dalam definisi "tidak dapat dipahami" dalam revisi 4 dapat dipilih untuk setiap M. Saya khawatir Anda membuat kesalahan mendasar di sini. Jika Anda masih kesulitan memahaminya, pos ini oleh Raphael dan tautan di dalamnya mungkin membantu. Saya memilih untuk menutup ini bukan pertanyaan nyata.

Tsuyoshi Ito

C n^{k}

$Cn^k$

C

$C$

k

$k$

Jawaban:

(Saya pensiun karena tidak lagi relevan dengan bagian jawaban yang baru saja menjelaskan mengapa tidak ada contoh masalah yang tidak dapat diputuskan / tidak ada algoritma polytime dengan batas waktu yang tidak dapat dihitung)

$T$ $M$ $M$ $T$

$M$ $M$
$M$ $M'$

Jadi sepertinya jawaban untuk pertanyaan Anda adalah "tidak": bahasa apa pun yang diputuskan dalam polytime oleh beberapa mesin diputuskan oleh mesin polytime yang terbukti. Tapi mungkin pertanyaan Anda seharusnya:

$M$ $M'$ $M$

Saya curiga jawabannya adalah ya, tetapi saat ini saya tidak punya waktu lagi untuk mencurahkan ini.

Sasho Nikolov
sumber

------ Ada dua pengertian berbeda dari kata yang tidak dapat diputuskan dalam matematika dan ilmu komputer. Yang pertama adalah bukti-teori yang digunakan dalam kaitannya dengan teorema Gödel, bahwa pernyataan tidak dapat dibuktikan atau disangkal dalam sistem deduktif yang ditentukan. ... Karena dua arti kata yang tidak dapat diputuskan, istilah independen kadang-kadang digunakan alih-alih diputuskan untuk arti "tidak dapat dibuktikan atau ditolak".

John Sidles

Terima kasih, Sasho! Saya juga menghargai hal ini, namun dalil tersebut dapat diubah melalui perbedaan Wikipedia: "Ada dua pengertian berbeda dari kata yang tidak dapat diputuskan dalam matematika dan ilmu komputer. Yang pertama adalah bukti-teori yang digunakan dalam kaitannya dengan teorema Gödel, bahwa pernyataan tidak dapat dibuktikan atau disangkal dalam sistem deduktif yang ditentukan ... Karena dua makna kata yang tidak dapat diputuskan, istilah independen kadang-kadang digunakan alih-alih diputuskan untuk arti 'tidak dapat dibuktikan atau ditolak'. " Karena itu saya berharap untuk mengklarifikasi pertanyaan hari ini.

John Sidles

Didorong sangat besar oleh komentar Anda yang penuh pertimbangan, atribut ambigu "decidable" sekarang telah digantikan oleh atribut (semoga tidak ambigu) 'tidak dapat dibuktikan atau disangkal.' Terima kasih atas bantuan Anda dan terima kasih.

John Sidles

silakan periksa jawaban saya yang diperbarui

Sasho Nikolov

Terima kasih, Sasho. Saya juga harus istirahat sampai besok, namun saat pertama kali membaca saran terakhir Anda tampaknya sangat bermanfaat, dan saya berharap untuk segera menanggapinya. Terima kasih lagi.

John Sidles

Hanya komentar panjang yang mencoba menafsirkan pertanyaan itu.

$M$ ~~dijanjikan untuk berhenti~~ $M$ ~~bilangan real semidefinite positif~~ $r$ ~~pertanyaan~~ $Q_{M,r}$

PILIHAN 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

PILIHAN 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

Dan jika Anda bertanya: "Oke, tapi bisakah kita menghitung nilai 1 atau 0 untuk membangun algoritme yang menjawab pertanyaan Opsi 2?", Lalu kita kembali ke ini:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Marzio De Biasi
sumber

Marzo, terima kasih atas jawaban ini dan atas komentar Anda di atas. Istilah ambigu "decidable" telah dihapus --- artinya berbeda untuk komunitas yang berbeda --- mendukung idiom bukti-teoretis "tidak dapat dibuktikan atau disangkal". Untuk antrian untuk mengklarifikasi amandemen untuk versi pertanyaan yang diedit besok (yang diharapkan akan menjadi pose terakhir yang sulit dari pertanyaan) frase "Untuk semua n " akan ditambahkan, sesuai Opsi Anda 1. Dan akhirnya, penghargaan dan terima kasih diperluas untuk Anda, dan untuk semua orang, untuk bantuan dalam mengajukan pertanyaan dengan seksama dan jelas.

John Sidles

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzo, oke dan terima kasih. Juga, untuk menetapkan "Implikasi Viola," kita harus menyesuaikan argumen dari Bagian 3 dari catatan mata kuliah Jeremy Avigad (sebagaimana terkait dalam pertanyaan) dengan konstruksi Viola ... pertanyaan yang diubah akan memperjelas poin ini. Tak perlu dikatakan, proses klarifikasi definisi telah 10X ++ lebih sulit daripada yang saya perkirakan sebelumnya ... yang mungkin merupakan poin utama dari pertanyaan. Terima kasih lagi.

John Sidles

Jawaban untuk pertanyaan Anda # 1 jelas "tidak." Seperti yang saya percaya seseorang tunjukkan di bagian komentar (sangat panjang), Anda dapat dengan mudah menambahkan "polylimiting" ke mesin. Yaitu, bahkan jika Anda tidak tahu apa itu r, jika Anda menebak bilangan bulat yang lebih besar dari r (ini tentu saja mungkin), Anda dapat mengatur mesin overhead yang mensimulasikan mesin Turing "yang tidak dapat dipahami" Anda, dan memaksanya untuk berhenti berjalan dalam waktu polinomial ... tanpa mengubah bahasa yang diterima mesin Turing sama sekali. Dengan cara ini, Anda dapat mengonversi mesin polinomial waktu "Turing" menjadi "polinomial" waktu Turing, yang berarti bahwa tidak ada bahasa dalam P yang dapat diputuskan dengan mesin Turing eksklusif yang "tidak dapat dipahami".

Saya harap ini membantu. Kecuali saya benar-benar salah mengartikan pertanyaan dan niat Anda, jawaban saya tentu saja benar; itu sama sekali bukan pertanyaan terbuka.

Philip White
sumber

Ngomong-ngomong, jika Anda menginginkan contoh yang baik dari kandidat untuk apa yang Anda sebut algoritma "tidak dapat dipahami", lihat scholarpedia.org/article/Universal_search . Algoritme pencarian universal untuk menyelesaikan SAT mematuhi definisi Anda tentang iff P = NP yang secara formal independen.

Philip White

apakah Anda tahu sesuatu tentang pertanyaan terakhir dari jawaban saya? Saya percaya itu adalah satu-satunya pertanyaan yang masih belum jelas sepele ... bagi saya itu

Sasho Nikolov

@ Philip White, definisi ini dibuat dengan hati-hati untuk menghindari konstruksi yang Anda berikan. Karena seandainya runtime M tidak dapat ditentukan untuk beberapa eksponen r , dan kami menebak nilai r ' > r , dan kami memasang r' -polylimiter di mesin yang dimodifikasi M 'yang mengenali bahasa yang sama dengan M, lalu untuk M' pernyataan "runtime dari M 'adalah O (n ^ r) sehubungan dengan panjang input n" masih belum dapat ditentukan. Saya setuju, bahwa kita perlu berpikir dengan hati-hati tentang apakah SEMUA permainan kucing-dan-tikus dengan polylimiter yang ditentukan oracle dikecualikan (seperti maksudnya) --- jadi saya mengubah jawaban Anda!

John Sidles

Oh, dan karena komentar Sasho tumpang tindih dengan saya, tolong izinkan saya menyatakan penghargaan saya atas pertanyaan terakhir dalam jawaban Sasho , yang (menurut pemahaman saya sekarang) dengan sopan menghalangi pengenalan polimiter turunan oracle. Seperti sebelumnya, saya harus memikirkan ini selama satu atau dua hari. Sekali lagi terima kasih, Philip.

John Sidles

Maaf, saya seharusnya membaca jawaban Sasho Nikolov lebih hati-hati; Saya hanya melihat kata "ya," oops. Saya akan melihat pertanyaan terakhir sebentar lagi dan melihat apakah saya punya sesuatu yang berguna untuk dikatakan.

Philip White