New answers tagged complexity-classes
1
The answer depends on the coding of $n$.
The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n
\text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.
0
NP is not the subset of co-NP unless we assume A be an NP-Complete problem and A∈ co-NP (which is not possible) then we can say all NP problems are a subset of co-NP problems since we can reduce all NP problems to problem A which is NP-complete it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its ...
Top 50 recent answers are included