# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

399 questions
Filter by
Sorted by
Tagged with
34 views

### What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

Is it known if complexity class of all sparse languages is contained within e.g. $\mathsf{EXP}$ or $\mathsf{EXPSPACE}$? Or what is the smallest time or space complexity class that contains complexity ...
337 views

### Are there any known W[3] or W[3]-hard problems?

We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3]...
15 views

### Is QMA known to contain Co-NP?

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
81 views

### Conway's Game of Life: Is it really P-complete?

Wikipedia claims that the Game of Life is P-complete (or the decision problem version of it is; the function version, I suppose, would then be FP-complete). Colloquially, P-complete and FP-complete ...
44 views

### Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the ...
37 views

### If B ∈ NP and A <= B then A ∉ EXP?

If B ∈ NP and A <= B then A ∉ EXP. True, false or we don't know?
38 views

### If A ∉ NP then A ∈ co-NP. True, false or we don't know?

If A ∉ NP then A ∈ co-NP. True, false or we don't know?
40 views

### If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?

If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$, $Y$ is polynomial-time reducible to $Z$? If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$? True, false or we ...
34 views

### If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?

If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?
36 views

### If X is polynomial reduction to Y and Y is in NP, then X is in NP?

If X is polynomial reduction to Y and Y is in NP, then X is in NP? Is this true, false or "we don't know"? Why?
42 views

### Complexity of approximating a function value using queries

I am looking for information on problems of the following kind. There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
21 views

### Complexity of generating power sets

Suppose I have two sets $A$ and $B$ containing integers. Let $B'$ be the power set of $B$. Then suppose I have an algorithm that enumerates all possible pairings of elements in $A$ and $B'$ to apply a ...
23 views

### A question regarding definition of Deterministic Subexponential Time (SUBEXP)

First Look at the definition of SUBEXP from Complexity Zoo: SUBEXP: (Deterministic Subexponential-Time) The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$>0. (Note that the algorithm ...
34 views

### Arthur-Merlin protocol

I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$. We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not ...
50 views

### Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP

I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP. The equation has total n variables and each clause is a 2SAT equation ...
22 views

32 views

### $\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
62 views

### Logarithmic space verifier with unbounded witness

this is a HW question, but its considered a bonus question so I'd appreciate a direction. Definitions: The actual question: **Images taken from HW in TAU Complexity course by Amnon Ta-Shma. My ...