Masalah antara L dan NL

26

Hal ini juga diketahui bahwa diarahkan st-konektivitas adalah -Lengkap. Hasil terobosan Reingold menunjukkan bahwa diarahkan st-konektivitas dalam L . Planar diarahkan st-konektivitas dikenal di U L c o U L . Cho dan Huynh mendefinisikan masalah ransel parametrized dan dipamerkan hirarki masalah antara L dan N L .NLLULcoULLNL

Saya mencari lebih banyak masalah yang menengah antara dan N L yaitu, masalah yang adalah:LNL

  • dikenal di tetapi tidak diketahui (atau tidak mungkin) menjadi N L -Lengkap danNLNL
  • diketahui -Hard tetapi tidak diketahui berada di L .LL
Siwa Kintali
sumber

Jawaban:

13

Masalah RL-lengkap reachability dalam grafik diarahkan dengan polinomial pencampuran-waktu (ditunjukkan oleh Reingold, Trevisan, dan Vadhan di Pseudorandom berjalan di digraf reguler dan masalah RL vs L ) dalam ruang (lihat BPHSPACE ( S ) DSpace ( S 3 / 2 ) oleh Saks dan Zhou ), yang secara ketat antara L dan Savitch ini terikat pada NL dari O ( log 2 n ) ruang.log3/2(n)BPHSPACE(S)DSPACE(S3/2)O(log2n)

Derrick Stolee
sumber
10

O(log2n/loglogn)RUSPACE(logn)DSPACE(log2n/loglogn)

Derrick Stolee
sumber
1
Lihat juga: Lange, "Kelas Tidak Jelas yang Memiliki Set Lengkap" STACS '97.
Derrick Stolee
6

ULULcoULL

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: Pencocokan Sempurna dalam Grafik Planar Bipartit adalah dalam UL. Kolokium Elektronik tentang Kompleksitas Komputasi (ECCC) 17: 201 (2010)

SamiD
sumber
Saya kira saya harus sedikit malu dengan jawaban basi - tetapi hanya demi kelengkapan.
SamiD