Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

446 questions
Filter by
Sorted by
Tagged with
44 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 ...
• 109
1 vote
27 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 ...
• 719
1 vote
510 views

What does O( n^{1+o(1)} ) mean

The latest development in solving the max-flow problem promises a ${\displaystyle O(E^{1+o(1)}\log U)}$ solution. What does it mean, this $O(n^{1+o(1)})$-complexity?
• 27.6k
121 views

Complexity of the (Complete/Assign) 3-SAT problem?

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 ...
1 vote
28 views

• 2,824
23 views

• 21
55 views

Sufficient condition for a complexity class's closure under NP-reductions?

Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
21 views

Is $E^{quasiP}$ equal $E$ or larger?

Let $quasiP$ be the quasipolynomial time complexity class. Is $E^{quasiP}=E$ false? Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k>1$?
• 2,824
I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?