New answers tagged

0 votes

$NL$ Leaf languages and $PSPACE$

You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the ...
Steven's user avatar
  • 28.2k
0 votes

Lower Bound on Parity of Boolean Functions

This is false, various construction for computing simultaneously the same function on disjoint sets of variables are discussed in this cstheory.stackoverflow question.
Vladimir Lysikov's user avatar

Top 50 recent answers are included