Saya bertanya-tanya apakah ada pembenaran untuk percaya bahwa atau untuk percaya bahwa N L ≠ L ?
Diketahui bahwa . Literatur tentang derandomization dari R L ini cukup meyakinkan bahwa R L = L . Adakah yang tahu tentang beberapa artikel atau ide yang meyakinkan bahwa N L ≠ L ?
Pertama, izinkan saya mengutip skeptisisme bahwa . Seperti yang telah ditunjukkan bahwa konektivitas grafik yang tidak diarahkan ada di L (Reingold), dan bahwa N L = c o N L (Immerman-Szelepcsényi), saya berpikir bahwa kepercayaan pada L ≠ N L hanya menurun. Beberapa peneliti terkemuka tidak pernah memiliki keyakinan kuat. Misalnya, Juris Hartmanis (pendiri departemen CS di Cornell and Turing pemenang penghargaan) mengatakan:
Kami percaya bahwa NLOGSPACE berbeda dari LOGSPACE, tetapi tidak dengan kedalaman keyakinan yang sama dengan kelas kompleksitas lainnya. (Sumber)
Saya tahu dia mengatakan hal yang sama dalam literatur sejauh 70-an.
Ada beberapa bukti terhadap , meskipun tidak langsung. Telah ada pekerjaan untuk membuktikan batas bawah ruang untuk konektivitas s - t (masalah kanonik N L - lengkap) dalam model komputasi terbatas. Model-model ini cukup kuat untuk menjalankan algoritma teorema Savitch (yang memberikan algoritma ruang O ( log 2 n ) ) tetapi terbukti tidak cukup kuat untuk melakukan asimptotik yang lebih baik. Lihat kertas "Batas Bawah Ketat untuk Konektivitas st pada Model NNJAG". NNJAG ini batas bawah menunjukkan bahwa, apakah itu mungkin untuk mengalahkan teorema Savitch dan bahkan mendapatkan , salah satu pasti akan harus datang dengan sebuah algoritma yang sangat berbeda dari Savitch.
Namun, saya tidak tahu tentang konsekuensi formal yang tidak terduga dan tidak terduga yang berasal dari (kecuali yang jelas). Sekali lagi, ini adalah terutama karena kita sudah tahu hal-hal seperti N L = c o N L .