Apa masalah terbuka tertua di TCS?

Masalah ini terinspirasi oleh pertanyaan MO ini , yang menurut saya sangat menarik.

Apa masalah terbuka tertua di TCS?

Jelas pertanyaan ini membutuhkan klarifikasi.

Pertama, apa itu TCS? Saya pikir keberadaan angka sempurna ganjil bukanlah TCS. Saya akan mengatakan bahwa masalah kesepuluh Hilbert adalah TCS. Saya pikir masalah seperti "Bisakah kita membangun X dengan penggaris dan kompas" juga TCS, karena mereka meminta algoritma dalam model komputasi yang dibatasi. Mungkin tidak ada cara ketat untuk mendefinisikan apa masalah TCS, tetapi gunakan penilaian Anda. Mungkin satu tes adalah "Jika ini diselesaikan, apakah kemungkinan besar akan muncul di STOC / FOCS? Apakah peneliti yang menyelesaikannya kemungkinan besar adalah seorang ilmuwan komputer teoretis?"

Kedua, apa yang "tertua"? Maksudku tertua menurut tanggal. Tanggal yang dinyatakan juga harus dapat diverifikasi, tetapi saya rasa ini tidak terlalu sulit.

Ketiga, apa itu "masalah terbuka"? Dengan "masalah terbuka", maksud saya masalah yang secara khusus dianggap terbuka pada suatu waktu. Mungkin itu muncul di akhir makalah di bagian masalah terbuka, atau mungkin ada bukti bahwa beberapa orang mengerjakannya dan gagal, atau mungkin ada bukti yang salah dalam literatur, yang menunjukkan bahwa itu telah dipelajari. Sebuah contoh dari sesuatu yang tidak sesuai dengan kriteria ini: "Orang Yunani mempelajari objek X dan Y. Z jelas merupakan objek perantara, tentu mereka bertanya-tanya apakah itu dapat dibangun." Jika tidak ada literatur tentang Z dari periode waktu itu, maka itu bukan masalah terbuka dari periode waktu itu.

Keempat, apa yang saya maksud dengan "masalah"? Maksud saya pertanyaan "ya / tidak" yang spesifik, dan bukan sesuatu seperti "Karakterisasi semua objek X dengan properti Y", karena pertanyaan seperti itu seringkali tidak memiliki jawaban yang memuaskan. Cukup sering akan ada ketidaksepakatan tentang apakah pertanyaan telah diselesaikan. Mari kita tidak membahas pertanyaan semacam itu di sini. Jika itu bukan pertanyaan ya / tidak, tetapi jelas bahwa itu benar-benar terbuka, itu juga baik. (Dalam hal ini tidak jelas, dengan "masalah" yang saya maksud adalah masalah yang dinyatakan secara formal. Tolong jangan mengonversi beberapa legenda rakyat tentang perjudian pada abad ke-16 menjadi pertanyaan tentang BPP dan PSPACE.)

Terakhir, karena ini bukan pertanyaan daftar besar, silakan posting jawaban hanya jika Anda pikir itu lebih tua dari jawaban yang sudah diposting (atau jika Anda berpikir jawaban yang diposting tidak memenuhi beberapa persyaratan lain - seperti mereka bukan TCS, atau tidak terbuka). Ini bukan kumpulan masalah terbuka lama tanpa pandang bulu.

Apa kompleksitas komputasi multiplikasi bilangan bulat? Dapat diperdebatkan, pertanyaan ini paling tidak berasal dari algoritma 'duplasi dan mediasi' untuk perkalian bilangan bulat yang dijelaskan dalam Rhind Mathematical Papyrus, yang ditulis sekitar tahun 1650 SM , tetapi mengklaim sebagai salinan dari dokumen yang jauh lebih tua.

Harus diakui, papirus Rhind tidak secara eksplisit mempertimbangkan kompleksitas algoritma. Jadi, mungkin jawaban yang lebih baik adalah Apa kompleksitas penyelesaian sistem persamaan linear? Penelitian tentang algoritma yang efisien untuk menyelesaikan sistem linier setidaknya berasal dari komentar Liu Hui, yang diterbitkan pada 263 M , pada The Nine Chapters on the Mathematical Art . Secara khusus, Liu Hui membandingkan dua varian dari apa yang sekarang dikenal sebagai eliminasi Gaussian, dan menghitung jumlah operasi aritmatika yang digunakan oleh masing-masing, dengan tujuan eksplisit untuk menemukan metode yang lebih efisien.

Kedua pertanyaan ini masih menjadi target penelitian aktif.

Pencarian untuk algoritma yang efisien untuk anjak piutang tampaknya kembali ke setidaknya Gauss. Artikel 329 Gauss ' Disquitiones Arithmeticae (1801) memiliki kutipan ( sumber ) berikut:

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. ... Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Tentu saja, memang benar bahwa Gauss tidak secara resmi mendefinisikan apa yang diinginkannya dari algoritma anjak piutang. Dia memang berbicara dalam artikel yang sama tentang fakta bahwa semua algoritma pengujian purba yang dikenal pada waktu itu sangat "melelahkan dan prolix".

Berikut ini, dikutip dari

• Goldwasser, S. dan Micali, S. 1982. Enkripsi probabilistik & cara bermain poker mental menjaga rahasia semua informasi parsial. Dalam Prosiding Simposium ACM Tahunan Keempat Belas tentang Teori Komputasi (San Francisco, California, Amerika Serikat, 05 - 07 Mei 1982). STOC '82. ACM, New York, NY, 365-377. DOI = http://doi.acm.org/10.1145/800070.802212

Mengacu pada masalah lain sejak Gauss 'Disquitiones Arithmeticae (1801):

$(\frac{q}{N})=1$$(\frac{q}{N})$

PS: Sekarang, kita tahu dua dari empat masalah algoritmik :

1. Anjak piutang (sebagaimana disebutkan oleh arnab);
2. Memutuskan residu kuadratik.

apa dua masalah yang tersisa yang dijelaskan oleh Gauss?

Dalam literatur negara kita, ada pepatah, yang secara harfiah diterjemahkan sebagai "Teka-teki menjadi mudah ketika dipecahkan." Meskipun bukan terjemahan yang baik, ini merujuk pada fakta bahwa ketika Anda memiliki solusinya, Anda dapat dengan mudah memverifikasinya; namun sebelum itu, teka-teki itu tampak sangat sulit.

Ini merujuk pada masalah "FP vs. FNP" yang sekarang terkenal: Jika FNP = FP, verifikasi jawaban atas teka-teki itu semudah menemukannya. Namun jika FNP ≠ FP, maka ada "teka-teki" yang menemukan solusi jauh lebih sulit daripada memverifikasi solusi.

Saya percaya masalah ini adalah masalah terbuka TCS tertua, namun perumusannya yang teliti dimulai sekitar 30 tahun yang lalu!

There seems to be a similar (yet somehow different!) proverb in the English language: "It's easy to be wise after the event" or "It's easy to be smart after the fact."

EDIT: "Bisakah kita faktor angka dalam waktu-poli" adalah masalah terbuka TCS lain, namun saya pikir ini lebih muda dari masalah yang disebutkan di atas.

Berikut dua daftar masalah terbuka TCS di web:

• http://www.c2.com/cgi/wiki?OpenProblemsInComputerScience
• http://garden.irmacs.sfu.ca/?q=category/theoretical_computer_science

Kami juga memiliki daftar di CSTheory.

Saya mempertanyakan teori bilangan Anda yang tidak termasuk yang melibatkan pertanyaan apakah beberapa set teoritik angka terbatas atau tidak terbatas sebagai bagian dari TCS dan pasti akan berdebat sebaliknya. orang-orang Yunani mempertanyakan apakah:

• apakah ada angka sempurna yang aneh? [mungkin dipertimbangkan oleh Euclid]

• apakah ada jumlah prima kembar yang tak terbatas?

$TM_x$$TM_y$

jadi bisa dibilang ini adalah dua masalah algoritmik kuno dan orang-orang Yunani memelopori TCS paling awal terutama dalam bentuk teori bilangan dan masalah teori bilangan awal hanyalah kasus khusus dari Turings yang menghentikan masalah, dan bukti awal awal untuk kesulitannya. dan ada hubungan erat antara menanyakan tentang / menemukan / mencari bukti dan teori yang tidak dapat dipungkiri.

bisa dibilang penelitian baru menunjukkan dugaan collatz, pernah dianggap sebagai keingintahuan teori bilangan, memiliki hubungan mendalam dengan teori komputabilitas, & mungkin terletak tepat di batas antara masalah yang tidak dapat diputuskan dan masalah yang dapat diputuskan. juga contoh Anda mengutip masalah ke-10 hilberts menunjukkan hubungan yang sangat mendasar antara teori bilangan dan TCS.

dua pertanyaan algoritmik kuno lainnya:

• apa itu algoritma efisien, atau paling efisien untuk komputasi gcd, pembagi umum terbesar?

• apa itu algoritma yang efisien, atau paling efisien untuk komputasi bilangan prima?

menyetujui pertanyaan ke-2 cukup erat kaitannya dengan anjak piutang, tetapi tentu saja tidak sama. itu dianggap oleh saringan dan euclid eratosthenes. tentu saja itu baru-baru ini ditunjukkan dalam P oleh AKS, tetapi bahkan kemudian algoritma tidak terbukti sepenuhnya optimal.

ada penelitian TCS yang sangat modern tentang algoritma euclids gcd (yaitu abad ke-20) yang menunjukkan bahwa angka-angka fibonacci memberikan kinerja kasus terburuk. [tidak yakin siapa yang pertama menunjukkan ini]

sampai algoritma euclids terbukti optimal, perhitungan gcd yang efisien tetap terbuka.

Tidak yakin seberapa serius jawaban ini, tapi ....

Itu benar-benar tergantung seberapa luas Anda bersedia mendefinisikan pertanyaan Anda.

Tentunya "dapatkah seseorang membangun mesin yang cerdas?" adalah pertanyaan terbuka tertua di CS yang memulai ilmu komputer, tetapi mungkin berusia satu atau dua milenium daripada CS. Tidak? (Ini adalah pertanyaan teori, karena ia meminta jawaban - bukan untuk mesin itu sendiri ...)

Referensi alami untuk mencari mesin cerdas adalah Golem ... http://en.wikipedia.org/wiki/Golem#History

Saya dapat menjawab pertanyaan Anda dengan kepastian 100% untuk jangka waktu tertentu. Jika kita mempertimbangkan periode dari makalah seminal Hartmanis dan Stearns sampai titik mana pun di masa depan, masalah tertua dalam TCS yang masih terbuka adalah:

Berapa overhead minimum yang diperlukan untuk simulasi TM deterministik?

$T^{2}(n)$$T(n)$$\log T(n)$

$\log T(n)$