# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

344 questions
Filter by
Sorted by
Tagged with
197 views

### is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
108 views

### Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$

Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities. I think yes and here is what I think: It seems given that $\text{BPP}$...
566 views

### If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that ...
222 views

### $\mathsf{PP=RP}$ consequences

We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level. What are the other non-trivial ...
802 views

### If NP is not a proper subset of coNP, why does NP not equal coNP?

I am studying some lecture notes on the complexity of algorithms. The notes give a proof that NP is not a proper subset of coNP. However, they still assert that NP is a subset of coNP (which I agree ...
658 views

### Notation: SPACE(n) vs SPACE(O(n))

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not ...
184 views

374 views

### Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

$P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results. What is a rigorous proof for $P^{\#P}\subseteq P^{PP}$...
317 views

### Is NEXP = co-NEXP?

It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?
89 views

### What does $\cdot$ mean as a notation with complexity classes?

In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning. SO given two classes $A$ and $B$ ...
169 views

80 views

### Maximal class for which function equivalence is decidable

I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no. Here is my followup. What is the most ...
538 views

### Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...