Monotone Separation of Logarithmic Space from Logarithmic Depth

摘要

We show that the monotone analogue of logspace computation is more powerful than monotone log-depth circuits: monotone bounded fanin circuits for a certain function in monotone logspace require depth Ω(lg2n).