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 ...
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.
Top 50 recent answers are included
Related Tags
complexity-classes × 491complexity-theory × 402
time-complexity × 97
np × 53
space-complexity × 49
np-complete × 42
reductions × 31
turing-machines × 22
oracle-machines × 22
p-vs-np × 20
decision-problem × 15
reference-request × 14
closure-properties × 14
circuits × 14
quantum-computing × 14
np-hard × 13
polynomial-time × 13
computability × 12
approximation × 12
algorithms × 11
terminology × 11
randomized-algorithms × 11
probabilistic-algorithms × 11
graphs × 10
optimization × 10