Saya mencari dugaan tentang algoritme dan kompleksitas yang dipandang kredibel oleh banyak orang di beberapa titik waktu, tetapi kemudian mereka ditolak, atau setidaknya tidak dipercaya, karena pemasangan kontra-bukti. Berikut adalah dua contoh:
Hipotesis oracle acak: hubungan antara kelas-kelas kompleksitas yang berlaku untuk hampir semua dunia yang ter-relativisasi, juga berlaku dalam kasus yang tidak ter-relativisasi. Ini dibantah oleh hasil , dan dengan menunjukkan bahwa berlaku untuk hampir semua nubuat acak , lihat Random Oracle Hypothesis is False .I P X ≠ P S P A C E X X
Keacakan kesalahan terbatas benar memperluas kekuatan waktu polinomial (yaitu, ). Ini diyakini untuk sementara waktu, tetapi kemudian, karena hasil derandomisasi yang canggih dan koneksi mereka ke kompleksitas sirkuit, dugaan yang berlawanan ( ) telah menjadi lazim (meskipun masih terbuka).P = B P P
Manakah dugaan lain yang gagal dalam ujian waktu?
sumber
Jawaban:
sumber
Sebelum , dianggap mungkin bahkan tidak terkandung dalam : di Fortnow-Sipser 1988 mereka menduga ini sebagai kasus dan memberikan relatif oracle yang memang benar.IP=PSPACE coNP IP
sumber
Program percabangan dengan lebar konstan memerlukan lebih dari panjang polinomial untuk dihitung : Setelah Furst-Saxe-Sipser dan Ajtai pada tahun 1981 menunjukkan bahwa sirkuit AC 0 tidak dapat dihitung, langkah berikutnya yang wajar tampaknya adalah menunjukkan bahwa program percabangan lebar-lebar polinomial panjang tidak bisa dihitung, yang secara luas dikira masih ada. David Barrington pada tahun 1986 menunjukkan bahwa mereka tidak hanya dapat menghitung tetapi juga setara dengan NC 1 .
sumber
The -conjecture: Bahwa algoritma deterministik apa pun untuk membutuhkan waktu .3SUM 3SUM Ω(n2)
Ini dibantah pada tahun 2014, oleh Allan Grønlund dan Seth Pettie, yang memberikan algoritma deterministik yang berjalan dalam waktu [1].O(n2/(logn/loglogn)2/3)
[1] Segitiga Bertiga, Merosot, dan Cinta. Allan Grønlund dan Seth Pettie. Dalam Yayasan Ilmu Komputer (FOCS) 2014, hlm. 621-630. arXiv: 1404.0799 [cs.DS]
sumber
Solusi dari masalah kesepuluh Hilbert oleh Davis, Matiyasevich, Putnam, dan Robinson, menunjukkan bahwa perangkat yang dapat dihitung secara rekursif adalah perangkat Diophantine.
(Saya mereproduksi di sini sebuah posting blog , Hindsight , dari beberapa tahun yang lalu, seperti yang disarankan dalam komentar.)
Dari ulasan Georg Kreisel tentang Masalah keputusan untuk persamaan diophantine eksponensial , oleh Martin Davis, Hilary Putnam, dan Julia Robinson, Ann. dari Matematika. (2), 74 (3) , (1961), 425-436. MR0133227 (24 # A3061) .
Tentu saja, kutipan favorit saya sehubungan dengan masalah kesepuluh adalah dari Kata Pengantar oleh Martin Davis ke masalah kesepuluh Hilbert milik Yuri Matiyasevich .
sumber
Program Hilbert dan "dugaannya" tentang kepastian teori formal. Itu dirumuskan pada awal 1920-an dan dikejar olehnya dan rekan-rekannya di Universitas Gottingen dan di tempat lain pada 1920-an dan 1930-an.
"Dengan landasan matematika yang baru ini - yang dapat dengan tepat disebut sebagai teori pembuktian - saya percaya untuk membuang pertanyaan-pertanyaan mendasar dalam matematika seperti itu sekali dan untuk semua dengan mengubah setiap pernyataan matematika menjadi formula yang dapat diperagakan secara konkret dan keras, dan dengan demikian mentransfer seluruh pertanyaan kompleks ke dalam bidang matematika murni. "
Diketahui bahwa proposal Hilbert "jatuh" (agak cepat [1931]) ke dalam teorema ketidaklengkapan Godel .
Untuk tinjauan umum yang bagus tentang program Hilbert dan perkembangan selanjutnya, lihat: Richard Zach; Program Hilbert dulu dan sekarang; Handbook of Philosophy of Science. Volume 5: Filsafat Logika; 2006
Lihat juga jawaban Andrés Caicedo untuk aspek lain dari kisah ini: masalah kesepuluh Hilbert yang diselesaikan hanya pada tahun 1970.
sumber
Dalam sebuah ceramah oleh Madhu Sudan * ia mengklaim ada beberapa kepercayaan bahwa ada sehingga , melalui pemrograman semidefinite, sebelum bukti teorema PCP tiga bit Håstad.s>1/2 PCP1,s[logn,3]⊆P
Memang SDP memang menunjukkan , memberikan ikatan yang kuat pada kompleksitas PCP tersebut.PCP1,1/2[logn,3]=P
(* Saya menemukan kuliah Madhu ini diterbitkan dalam "Teori Kompleksitas Komputasi yang diedit oleh Rudich / Wigderson")
sumber
dugaan berkisar pada spektrum dari formal ke informal. misalnya dugaan Hilberts yang terkenal tentang desidabilitas matematika diformalkan menjadi beberapa masalah, misalnya masalah Hilberts ke-10 tetapi juga dugaan informal yang lebih muluk yang mencakup seluruh bidang. itu juga dapat dilihat sebagai program penelitian yang diusulkan.
satu resep mudah untuk menemukan "obituari kematian" dugaan seperti itu adalah dengan mempertimbangkan "meta-" pernyataan "[x] dugaan dapat dibuktikan dalam hidupku." literatur matematika penuh dengan pernyataan / harapan seperti itu yang ternyata "salah" dalam arti benar-benar menentang harapan tentang kesulitan dan aksesibilitas bukti. yang klasik adalah dugaan Riemann, terbuka selama lebih dari ~ 1½ abad. menerapkan model yang sama ini ke teori kompleksitas tidak semudah karena teori kompleksitas adalah bidang ilmiah yang jauh lebih muda. Namun, inilah contoh utama.
penemuan awal masalah P vs NP (sekarang buka 4½ dekade) memiliki semacam kepolosan karena para peneliti asli tidak dan tidak bisa membayangkan betapa sulit atau lintas-potong masalah akan berubah menjadi. untuk membuat ini lebih spesifik, pertimbangkan bidang kompleksitas sirkuit yang ditemukan pada awal 1980-an misalnya oleh Sipser. ini adalah program penelitian agak seperti Hilberts dipasang sebagian untuk menyerang P vs NP. beberapa hasil historis dirangkum oleh Arvind dalam abstrak / pengantar Kolom Kompleksitas Komputasi ini, BEATCS 106 :
ada dua kertas kunci yang menjatuhkan harapan di lapangan. Razborov mendapatkan hasil yang luar biasa tentang fungsi Clique tetapi kemudian menulis dua makalah yang saling bertentangan. satu makalah menunjukkan bahwa Matching, masalah P-time, membutuhkan sirkuit monoton eksponensial dan oleh karena itu dalam beberapa hal pendekatan sirkuit monoton untuk batas bawah digagalkan karena kurangnya korespondensi dalam kompleksitas dengan sirkuit nonmonotone ("lengkap") (masih belum sepenuhnya dipahami).
ini diperluas dalam makalahnya yang terkenal, Natural Proofs, yang ditulis bersama dengan Rudich di mana ditunjukkan bahwa semua bukti sirkuit sebelumnya dengan batas bawah tunduk pada pola tertentu yang memiliki kelemahan yang dapat dibuktikan dalam arti berkonflik dengan batas bawah terkira pada generator nomor acak dari kriptografi.
jadi, pada tingkat tertentu sirkuit telah "jatuh dari rahmat". ini masih merupakan wilayah penelitian masif, tetapi kearifan konvensional, yang didukung oleh hasil teknis, adalah semacam pola / struktur pembuktian khusus yang belum diketahui akan diperlukan untuk mendapatkan hasil yang kuat di bidang tersebut, jika mungkin bahkan mungkin. bahkan dengan cara yang sama orang mungkin menyarankan bahwa bahkan "batas bawah yang kuat dalam teori kompleksitas" secara keseluruhan sekarang terlihat sangat sulit, dan ini tidak banyak diharapkan / diprediksi pada masa muda bidang tersebut. tetapi di sisi lain ini kemudian peringkat mereka di sana dalam kesulitan / signifikansi / pentingnya dengan masalah (terbuka) matematika yang besar.
sumber