Pertimbangkan mesin (yaitu, algoritma probabilistik yang menggunakan logspace dan banyak bit acak secara polinomi). Diketahui (Saks-Zhou) bahwa .
Pertanyaan saya adalah tentang mesin yang hanya menggunakan banyak bit keacakan polylog. Dalam salah satu makalah Goldreich, disebutkan secara sepintas bahwa bahasa yang diputuskan oleh mesin sebenarnya dalam logspace L deterministik . Tetapi saya tidak dapat menemukan penjelasan apa pun dari pernyataan ini di mana saja.
Mengapa ia dapat diacak sepenuhnya dalam ruang log?