Algoritma logspace yang efisien

Mudah untuk melihat bahwa masalah apa pun yang dapat ditentukan dalam deterministic logspace ( ) berjalan paling banyak pada waktu polinomial ( P ). Banyak algoritma diketahui logspace (Misalnya: diarahkan st-konektivitas, planar grafik isomorfisma) berjalan dalam O ( n k ) di mana k gila-gilaan besar.$L$$P$$O(n^k)$$k$

• Saya mencari contoh masalah alam yang diketahui dipecahkan secara bersamaan dalam logspace deterministik dan waktu di mana k ≤ 10 . Tidak ada yang istimewa tentang 10. Melihat algoritma logspace yang saat ini dikenal, saya pikir k ≤ 10 cukup menarik.$O(n^k)$$k \leq 10$$k \leq 10$
• Aleliunas et al. menunjukkan bahwa tidak diarahkan st-konektivitas dalam (acak logspace). Waktu berjalan dari algoritma mereka adalah O ( n 3 ) . Apakah ada masalah alami yang dapat diselesaikan secara bersamaan dalam R L dan waktu linear (atau) dekat waktu linier yaitu, O ( n log i n ) waktu?$RL$$O(n^3)$$RL$$O(n{\log}^i{n})$

Sunting: Untuk membuat hal-hal lebih menarik mari kita lihat masalah yang setidaknya -hard.$NC^1$

Saya kira jangkauan tunggal Single-sink Planar DAG (SSPD) reachability memiliki algoritma logspace dengan waktu berjalan yang sederhana ( ?). Saya tidak begitu yakin tentang algoritma Singleach-source Planag DAG Reachability (SMPD).$O(n^2)$

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Masalah Jangkauan Planar dan Grid Graph. Teori Komputasi. Syst. 45 (4): 675-723 (2009)

Juga, algoritma ruang log baru untuk pengujian planaritas dan proses embedding berjalan dalam waktu polinomial sederhana (tentu saja modulo jangkauan tak terarah)

Ref: Samir Datta, Gautam Prakriya: Pengujian Planaritas Revisited CoRR abs / 1101.2637: (2011)

Akhirnya, di sini adalah masalah mainan sederhana yang memiliki algo logspace dengan waktu berjalan sederhana (modulo jangkauan tidak terarah) yaitu. Isomorfisme Outerplanar.

Jawaban ini lebih merupakan masalah mainan daripada masalah penelitian nyata.

Contoh khas saya dari algoritma ruang log untuk diberikan kepada teman programmer adalah teka-teki berikut:

Diberikan daftar tertaut dengan ukuran yang tidak diketahui ( ) dan menggunakan jumlah variabel penunjuk yang konstan, tentukan apakah daftar tertaut itu pernah berulang.$n$

Solusinya adalah algoritma ruang-log, menggunakan dua pointer berukuran- untuk menghubungkan node daftar. Mulai keduanya di awal daftar tertaut dan lakukan prosedur berulang berikut:$O(\log n)$

• Tingkatkan pointer pertama dalam daftar dengan satu langkah.
• Majukan pointer kedua dalam daftar dengan dua langkah.
• Jika salah satu pointer menemukan ujungnya, kembalikan false.
• Jika node menunjuk ke node yang sama, kembalikan true.
• Jika tidak, lakukan lagi.

$n$$n$

$O(n)$

$NC^1$