Kompleksitas ruang rata-rata

11

Saya mencoba menemukan masalah yang kompleksitas ruang kasus rata-ratanya telah dianalisis.

Lebih khusus, saya tertarik untuk mengetahui apakah ada masalah dengan kompleksitas ruang yang terbukti batas bawahnya yang super-linear, dan terutama jika ada dengan analisis kasus rata-rata (misalnya, terikat berlaku bahkan jika algoritma diizinkan untuk melakukan kesalahan dalam persentase kecil kali, dll.)

Terima kasih sebelumnya

cc.complexity-theory reference-request space-bounded average-case-complexity pengguna4359
sumber
2
Jika Anda bisa lebih spesifik, saya pikir Anda akan lebih mungkin mendapatkan jawaban atas pertanyaan Anda. Dengan "kompleksitas ruang kasus rata-rata" dari suatu masalah, apakah maksud Anda rata-rata ruang minimum yang diperlukan untuk menyelesaikan setiap himpunan instance dari beberapa masalah? Saya tidak yakin itu didefinisikan dengan baik, meskipun itu bukan sesuatu yang saya pikirkan dengan sangat rinci. Jika Anda bermaksud sesuatu yang lebih sederhana, seperti kompleksitas ruang rata-rata dari algoritma tertentu saat menyelesaikan masalah, maka saya pikir pertanyaan Anda mungkin tidak mendapatkan banyak jawaban karena ada begitu banyak kemungkinan. (berlanjut di komentar berikutnya)
jbapple
(lanjutan dari atas) Secara khusus, jika itu yang Anda maksud, pertanyaan Anda mungkin agak terlalu umum untuk TCS SE: cstheory.stackexchange.com/faq Mungkin, mungkin tidak. Contoh pertama yang muncul di kepala saya adalah ftp.cs.umd.edu/pub/skipLists/skiplists.pdf , tetapi banyak struktur data acak memiliki analisis ruang.
jbapple
3
@ jbapple: Saya tidak bisa mengikuti kritik Anda. Saya pikir sudah jelas dari pertanyaan bahwa penanya mencari karya tentang kompleksitas ruang dari kompleksitas waktu rata-rata kasus Levin, dan masih berpikiran demikian bahkan setelah membaca komentar Anda. Saya tidak bisa menjawab pertanyaan bukan karena pertanyaannya tidak jelas, tetapi karena saya tidak tahu subjeknya dengan baik dan saya tidak tahu pekerjaan seperti itu.
Tsuyoshi Ito
@ Tsuyoshi Ito: Anda benar.
jbapple
menafsirkan "analisis kasus rata-rata" sebagai "algoritme dibiarkan salah beberapa kali" membuatnya terdengar seperti analisis acak.
Suresh Venkat

Jawaban:

7

Saya tertarik tetapi tidak akrab dengan topik ini. Mencari "Teori kompleksitas kasus rata-rata", saya menemukan tesis yang ditulis oleh Tomoyuki Yamakami:

Teori Kompleksitas Komputasi Kasus Biasa, Tomoyuki Yamakami, 1997.

Bagian 3.5.1 tampaknya relevan, gagasan ruang-analog mirip dengan kompleksitas waktu rata-rata didefinisikan. Semoga dengan membaca lebih dalam kita akan menemukan beberapa masalah yang telah dianalisis :)

Juga di koran

Pada Teori Kompleksitas Kasus Rata-Rata , Shai Ben-David, Benny Chor, Oded Goldreich, dan Michael Luby, 1989.

Kompleksitas ruang-log rata-rata didefinisikan dalam Bagian 7.

Hsien-Chih Chang 張顯 之
sumber