Ketelitian mengarah pada wawasan

Di MathOverflow, Timothy Gowers mengajukan pertanyaan berjudul " Mendemonstrasikan kekakuan itu penting ". Sebagian besar diskusi di sana tentang kasus-kasus yang menunjukkan pentingnya pembuktian, yang mungkin tidak perlu diyakinkan oleh orang-orang di CSTheory. Dalam pengalaman saya bukti perlu lebih ketat dalam ilmu komputer teoretis daripada di banyak bagian matematika kontinu, karena intuisi kita sering ternyata salah untuk struktur diskrit, dan karena dorongan untuk membuat implementasi mendorong argumen yang lebih rinci. Seorang ahli matematika mungkin puas dengan bukti keberadaan, tetapi seorang ilmuwan komputer teoretis biasanya akan mencoba menemukan bukti konstruktif. The Lovász Local Lemma adalah contoh yang bagus [1].

Karena itu saya ingin tahu

Adakah contoh spesifik dalam ilmu komputer teoretis di mana bukti yang kuat dari pernyataan yang dipercayai benar telah menyebabkan wawasan baru tentang sifat dari masalah yang mendasarinya?

Contoh terbaru yang tidak langsung dari algoritma dan teori kompleksitas adalah sintesis bukti-teoretis , turunan otomatis dari algoritma yang benar dan efisien dari pra dan pasca kondisi [2].

• [1] Robin A. Moser dan Gábor Tardos, Bukti Konstruktif dari General Lovász Local Lemma , JACM 57 , artikel 11, 2010. http://doi.acm.org/10.1145/1667053.1667060
• [2] Saurabh Srivastava, Sumit Gulwani, dan Jeffrey S. Foster, Dari verifikasi program hingga sintesis program , ACM SIGPLAN Pemberitahuan 45 , 313–326, 2010. http://doi.acm.org/10.1145/1707801.1706337

Edit:Jenis jawaban yang saya pikirkan adalah seperti yang ditulis oleh Scott dan Matus. Seperti yang disarankan Kaveh, ini adalah triple dari sesuatu yang orang ingin buktikan (tetapi yang tidak selalu tidak terduga oleh "fisika", "handwaving", atau "intuitif" argumen), bukti, dan konsekuensi untuk "masalah mendasar" yang mengikuti dari bukti yang tidak diantisipasi (mungkin membuat bukti diperlukan ide-ide baru yang tidak terduga, atau secara alami mengarah ke suatu algoritma, atau mengubah cara kita berpikir tentang area). Teknik yang dikembangkan saat mengembangkan bukti adalah blok bangunan ilmu komputer teoretis, sehingga untuk mempertahankan nilai pertanyaan yang agak subyektif ini, ada baiknya berfokus pada pengalaman pribadi, seperti yang diberikan oleh Scott, atau argumen yang didukung oleh referensi, seperti yang dilakukan matus. Apalagi saya Saya berusaha menghindari pertengkaran tentang apakah sesuatu memenuhi syarat atau tidak; Sayangnya, sifat pertanyaannya pada hakekatnya bisa problematis.

Kami sudah memiliki pertanyaan tentang hasil "mengejutkan" dalam kompleksitas: Hasil Mengejutkan dalam Kompleksitas (Bukan pada Daftar Blog Kompleksitas) jadi idealnya saya mencari jawaban yang berfokus pada nilai bukti yang kuat , belum tentu ukuran terobosan.

András, seperti yang mungkin Anda ketahui, ada begitu banyak contoh tentang apa yang Anda bicarakan sehingga hampir mustahil untuk mengetahui dari mana harus memulai! Namun, saya pikir pertanyaan ini sebenarnya bisa menjadi pertanyaan yang bagus, jika orang memberikan contoh dari pengalaman mereka sendiri di mana bukti dugaan yang diyakini secara luas dalam subarea mereka menghasilkan wawasan baru.

Ketika saya masih mahasiswa, masalah TCS nyata pertama yang saya tangani adalah ini: apa algoritma kuantum tercepat untuk mengevaluasi OR pada AND dari variabel Boolean masing-masing? Sangat jelas bagi saya dan semua orang yang saya ajak bicara bahwa yang terbaik yang dapat Anda lakukan adalah menerapkan algoritma Grover secara rekursif, baik ke OR maupun ke AND. Ini memberi batas atas O (logn log (n)). (Sebenarnya Anda dapat mengurangi faktor log, tapi mari kita abaikan itu untuk saat ini.)

Namun, untuk frustrasi yang luar biasa, saya tidak dapat membuktikan batas bawah yang lebih baik daripada yang sepele vi (n ^1/4 ). "Going physicist" dan "handwaving the answer" tidak pernah tampak lebih menarik! :-D

Tetapi kemudian, beberapa bulan kemudian, Andris Ambainis keluar dengan metode musuh kuantumnya , yang aplikasi utamanya pada awalnya adalah Ω (√n) batas bawah untuk OR-of-ANDs. Untuk membuktikan hasil ini, Andris membayangkan memberi makan suatu algoritma kuantum suatu superposisi dari input yang berbeda; ia kemudian mempelajari bagaimana keterikatan antara input dan algoritma meningkat dengan setiap query yang dibuat algoritma. Dia menunjukkan bagaimana pendekatan ini memungkinkan Anda kompleksitas permintaan kuantum yang lebih rendah bahkan untuk "berantakan," masalah non-simetris, dengan hanya menggunakan sifat-sifat kombinatorial yang sangat umum dari fungsi f yang berusaha dihitung oleh algoritma kuantum.

Jauh dari sekadar mengkonfirmasi bahwa kompleksitas kueri kuantum dari satu masalah yang menjengkelkan adalah apa yang diharapkan semua orang, teknik-teknik ini ternyata mewakili salah satu kemajuan terbesar dalam teori komputasi kuantum sejak algoritma Shor dan Grover. Mereka sejak itu telah digunakan untuk membuktikan lusinan batas bawah kuantum lainnya, dan bahkan digunakan untuk mendapatkan batas bawah klasik baru .

Tentu saja, ini "hanyalah hari lain di dunia matematika dan TCS yang indah." Bahkan jika setiap orang "sudah tahu" X itu benar, membuktikan X sangat sering membutuhkan teknik-teknik baru yang kemudian diterapkan jauh di luar X, dan khususnya untuk masalah-masalah di mana jawaban yang tepat adalah apriori yang jelas .

Pengulangan paralel adalah contoh yang bagus dari daerah saya:

$L$$x$$q_1$$q_2$$a_1$$a_2$$a_1$$a_2$$q_1,q_2$$x\in L$$x\not\in L$$s$

$s$$1$$s = 10^{-15}$$k$$q_1^{(1)},\ldots,q_1^{(k)}$$q_2^{(1)},\ldots,q_2^{(k)}$$a_1^{(1)},\ldots,a_1^{(k)}$$a_1^{(1)},\ldots,a_1^{(k)}$$k$

$s^{k}$$k$$s^{\Omega(k/\log|\Sigma|)}$$\Sigma$

$\Sigma$$k$

Kemudian, ada ekstensi yang menjadi mungkin: Anup Rao mampu mengadaptasi analisis untuk menunjukkan bahwa ketika sistem bukti asli adalah {\ em game proyeksi}, yaitu, jawaban dari prover pertama menentukan paling banyak satu jawaban yang dapat diterima dari pepatah kedua, tidak ada ketergantungan pada alfabet sama sekali, dan konstanta dalam eksponen dapat ditingkatkan. Ini penting karena sebagian besar kekerasan hasil perkiraan didasarkan pada game proyeksi, dan game unik adalah kasus khusus dari game proyeksi. Ada juga peningkatan kuantitatif dalam game pada ekspander (oleh Ricky Rosen dan Ran Raz), dan banyak lagi.

Lalu, ada konsekuensi jangka panjang. Hanya beberapa contoh: Sebuah lemma teoritik informasi dari makalah Raz digunakan dalam banyak konteks lain (dalam kriptografi, dalam ekuivalensi pengambilan sampel dan pencarian, dll). Teknik "sampling berkorelasi" yang digunakan Holenstein diterapkan dalam banyak karya lain (dalam kompleksitas komunikasi, dalam PCP, dll).

Contoh bagus lainnya dari kekakuan (dan teknik baru) yang diperlukan untuk membuktikan pernyataan yang diyakini benar: analisis yang lebih lancar. Dua kasus di titik:

• Algoritma simpleks
• Algoritma k-means

$k$$O(n^{c \cdot kd})$$n$

Saya pikir contoh berikut menelurkan banyak penelitian yang memiliki hasil seperti yang Anda cari, setidaknya jika saya mengikuti semangat contoh LLL Anda.

Robert E. Schapire. Kekuatan kemampuan belajar yang lemah. Pembelajaran Mesin, 5 (2): 197-227, 1990.

$\epsilon>0, \delta>0$$1-\delta$$\epsilon$$\epsilon$$\delta$$\delta$$\delta$$\gamma$

Bagaimanapun, banyak hal menjadi sangat menarik setelah karya Schapire. Solusinya menghasilkan mayoritas-mayoritas di atas hipotesis di kelas asli. Lalu datang:

Yoav Freund. Meningkatkan algoritma pembelajaran yang lemah oleh mayoritas. Informasi dan Komputasi, 121 (2): 256--285, 1995.

Makalah ini memiliki 'teguran' dari hasil Schapire, tetapi sekarang hipotesis yang dibangun hanya menggunakan mayoritas tunggal. Sejalan dengan ini, keduanya kemudian menghasilkan teguran lain, yang disebut AdaBoost:

Yoav Freund dan Robert E. Schapire. Generalisasi teoritik keputusan tentang pembelajaran online dan aplikasi untuk meningkatkan. Jurnal Ilmu Komputer dan Sistem, 55 (1): 119-139, 1997.

Pertanyaan pembelajaran yang lemah / kuat dimulai sebagai perhatian teoretis, tetapi urutan 'teguran' ini menghasilkan algoritma yang indah, salah satu hasil paling berpengaruh dalam pembelajaran mesin. Saya bisa menggunakan segala macam garis singgung di sini tetapi akan menahan diri. Dalam konteks TCS, hasil ini menarik banyak kehidupan dalam konteks (1) algoritma bobot multiplikatif dan (2) hasil set hard-core. Tentang (1), saya hanya ingin mengklarifikasi bahwa AdaBoost dapat dilihat sebagai contoh dari bobot multiplikasi / menampi hasil kerja Warmuth / Littlestone (Freund adalah seorang siswa Warmuth), tetapi ada banyak wawasan baru dalam meningkatkan hasil. Tentang (2), saya

Untuk akurasi sejarah, saya juga harus mengatakan bahwa tanggal pada kutipan saya mungkin tidak seperti yang diharapkan beberapa orang, karena untuk beberapa di antaranya ada versi konferensi sebelumnya.

Kembali ke sifat pertanyaan Anda. Nilai kunci dari 'rigor' di sini adalah dalam menyediakan kelas hipotesis yang dapat dipelajari (mayoritas tertimbang di atas kelas hipotesis asli) dan algoritma yang efisien untuk menemukannya.

Contoh ini sesuai dengan jawaban Dana dan Scott.

$n$$d$$d$$2^{n-1}$$d$$2$$n^{1/(d-1)}$$2^{n^{1/(d-1)}}$$1$$n^{1/(d-1)}$$d-1$$2^{n^{1/(d-1)}}$$2^{n^{1/(d-1)}}$$d$$2^{O(n^{1/(d-1)})}$

$d$$AC^0$

Rasborov dan Rudich paper "Natural Bukti" menawarkan bukti ketat (formalisasi) pernyataan sangat jelas "Ini benar-benar sulit untuk membuktikan bahwa P ≠ NP."

Gagasan bahwa beberapa masalah algoritmik membutuhkan sejumlah langkah eksponensial, atau pencarian yang teliti atas semua kemungkinan, dimunculkan sejak tahun 50-an dan mungkin sebelumnya. (Tentu saja, gagasan naif yang saling bersaing bahwa komputer dapat melakukan segalanya juga merupakan hal biasa.) Terobosan utama Cook dan Levin adalah menempatkan gagasan ini di atas dasar yang keras. Ini, tentu saja, mengubah segalanya.

Pembaruan: Saya baru menyadari bahwa jawaban saya seperti jawaban yang baik dari bahasa Turkis mengalamatkan judul pertanyaan "keras menuju wawasan" tetapi mungkin bukan kata-kata spesifik yang tentang "bukti kuat untuk sebuah teorema".

Alan Turing memformalkan gagasan algoritma (komputasi efektif) menggunakan mesin Turing. Dia menggunakan formalisme baru ini untuk membuktikan bahwa masalah Henti tidak dapat diputuskan (yaitu masalah Henti tidak dapat diselesaikan dengan algoritma apa pun). Ini mengarah pada program penelitian panjang yang membuktikan ketidakmungkinan masalah Hilbert ke-10. Matiyasevich pada tahun 1970 membuktikan bahwa tidak ada algoritma yang dapat memutuskan apakah persamaan Diophantine integer memiliki solusi integer.