New answers tagged complexity-classes
0
votes
Accepted
$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 ...
- 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.
- 156
Top 50 recent answers are included