# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

491 questions
Filter by
Sorted by
Tagged with
1 vote
28 views

### What's the intuition behind MIP* being bigger than MIP?

It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$. This was very confusing because it seemed like the (...
23 views

### $NL$ Leaf languages and $PSPACE$

I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505) 20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
1 vote
46 views

### How to prove MIP is in NEXP

I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
23 views

123 views

1 vote
41 views

### construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$

Problem This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell. Assume $L \in {\sf RP \backslash ZPP}$. Define  L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
1 vote
41 views

### Can all non-quantum physical systems be efficiently simulated on a classical computer?

Is it true that simulating classical physical systems is in P, i.e. can be done efficiently on Turing machines or are there known exceptions? I'm thinking of chaotic systems but I'm also curious more ...
25 views

### I'm trying solve a problem using different versions of SAT, how exactly does mixing SAT affect the hardness of the problem?

I'm trying to solve a problem which I can solve in 3SAT or as a mixed 2,3,4 SAT. I know how hard each of those categories are individually and know the derivations of their hardness individually. But ...
56 views

### Is there a theorem of the form "for any complexity class $C$ satisfying $X$, there exist $C$-complete problems"?

From what I've read, there are $C$-complete problems for all the complexity classes $C$ that I have looked at: $P$, $NP$, $EXPTIME$, $PSPACE$. But I also know that there is an infinite hierarchy of ...
145 views

### Difference between "almost-linear" and "quasilinear" time complexities

In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$. This is similar to the notion ...
53 views

### Given the current knowledge about complexity class, what can we say?

I am a CS student. I am looking at some questions my professor made and I got stuck in this one. "Which one of the following inclusions between complexity classes is coherent with the current ...
61 views

### Why isn't $P^A = A$?

I have a question regarding oracles. If I have the complexity class $P^A$ (with $P \subseteq A$), what is it's relationship to the class $A$? I mean it should be trivial that $A \subseteq P^A$ for all ...
1 vote
45 views

### What is different between two classes are 'incomparable' or two classes are 'not equal'?

Arora and Barak states (p. 230) the following: What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete ...
1 vote
The latest development in solving the max-flow problem promises a $O(E^{1+o(1)}\log U)$ solution. What does it mean, this $O(n^{1+o(1)})$-complexity?
A complete $k$-CNF formula on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies. Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a ...