Computational complexity classes and their relations

learn more… | top users | synonyms

1
vote
0answers
111 views

proving speedup phenomenon does not apply to any open complexity class separations

Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question. the Blum speedup ...
3
votes
0answers
108 views

How powerful are weak complexity classes with powerful oracles?

I am interested in complexity classes of the form $A^{B}$, where $A$ and $B$ are complexity classes such that $A \subsetneq \mathsf{P}$ and $\mathsf{NP} \subsetneq B$ are (believed to be) true. ...
4
votes
3answers
659 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
-2
votes
0answers
39 views

Is there a complexity bound on operation $\cdot$ in a ring that is anti-commutative and commutative?

For elementary arithmetic, we know the Big O-time/complexity for $+$ (addition) and $\cdot$ (mutliplication). (So we know the big-O time for calculating $1+2$ and $1 \cdot 3$.) What if we escape ...
4
votes
1answer
364 views

Example of #P-intermediate problem

The previous question Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P ...
0
votes
1answer
128 views

Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $. I wonder the following ...
2
votes
0answers
67 views

Padding Arguments for Probabilistic Classes

Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or ...
0
votes
0answers
49 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
10
votes
1answer
405 views

NP-complete problem with polynomially many certificates?

Let's call a language $L \in$ NP sparsely certificated if and only if: There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x ...
2
votes
1answer
185 views

Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup ...
5
votes
2answers
120 views

Is there an oracle separating Parity-P from PSPACE?

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
2
votes
0answers
82 views

Maximizing a #P-hard function

Suppose I have a #P-hard function $f(S,x)$ where $x\in T$. Is the problem of $\arg\max_x f(S,x)$ guaranteed to be intractable? If so, I want to see some references on this topic. If not, is there a ...
7
votes
1answer
156 views

Problems in AM or in MA

What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$? For $\mathsf{AM}$, I know the following two ...
10
votes
3answers
190 views

Examples of $\Sigma_2^p$ complete problems?

I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely: Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF ...
2
votes
1answer
103 views

Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem: Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' ...
16
votes
3answers
2k views

P and NP classes explanation through lambda-calculus

In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of ...
15
votes
1answer
353 views

Can constant ambiguity reduce the state complexity of a regular languages?

We say that NFA $M$ is Constantly Ambiguous if there exist $k\in \mathbb{N}$ such that any word $w\in \Sigma^*$ is accepted by either $0$ or (exactly) $k$ paths. If automaton $M$ is constantly ...
11
votes
1answer
293 views

Is $P^{NPI}$ different from $P^{NP}$?

Can we prove that for every language $L\in\mathsf{NP}$ that is not $\mathsf{NP}$-hard (this assumes $\mathsf P \ne \mathsf{NP}$), $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$? Alternately, can this be ...
0
votes
0answers
57 views

What problems are solvable as efficiently by primitive recursion as by a turing machine?

So the class $PR$ is the class of problems solvable by primitive recursion. This does not necessarily mean that primitive recursion solves all of these problems as efficiently as a turing machine ...
0
votes
0answers
119 views

ExpSpace problems whose configuration reachability problems are in P/poly?

Is anything known about ExpSpace problems whose configuration reachability problems are in P/poly? Let $M$ be an ExpSpace machine. Given two configurations $a$ and $b$ of $M$ (of max length), ...
0
votes
1answer
98 views

Complexity of a GLR parser on an ambiguous grammar

Let's consider the following expression grammar that is ambiguous: $E ::= E + E~|~a$ Although GLR parsing (recognition actually, I'm not interested in parse tree creation) is worst case $O(n^3)$, ...
5
votes
2answers
441 views

Is it right to call $2^{\sqrt{n}}$ “exponential”?

In his answer to a previous question, Sadeq Dousti recalled the following terminology: $f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.) $f(n) = ...
8
votes
0answers
197 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires ...
4
votes
2answers
193 views

Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class?

Do languages decidable in deterministic $n^{O(\log n)}$ time form an interesting complexity class? If yes, is there a name for this class and are there some interesting properties about it that we ...
26
votes
5answers
3k views

The unreasonable power of non-uniformity

From the common sense point of view, it is easy to believe that adding non-determinism to $\mathsf{P}$ significantly extends its power, i.e., $\mathsf{NP}$ is much larger than $\mathsf{P}$. After ...
1
vote
2answers
248 views

Lower-bound of a decision problem [closed]

What's the lower-bound of the decision problem that decides: Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = ...
8
votes
0answers
134 views

Complexity of unique coloring of graphs

The Isolation lemma of Mulmuley, Vazirani, and Vazirani can be used to show that certain $\mathsf{NP}$-complete problems can be reduced via randomized polytime reductions to the unique solution ...
9
votes
0answers
184 views

Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”. On the bottom of page 2 they remark that the results of Kannan imply that ...
1
vote
1answer
48 views

Complexity of Determining Linear Separability

Be $X := \{x_1,...,x_N\}$ and $Y := \{y_1,...,y_N\}$ subsets of $\mathbb{R}^d$. What is/are the most efficient existing algorithm/s for determining whether X and Y are linearly separable and what is ...
32
votes
4answers
964 views

Examples where the uniqueness of the solution makes it easier to find

The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. ...
1
vote
2answers
220 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist ...
8
votes
0answers
226 views

How powerful is exact “quantum” computing if you suspend unitarity?

Short Question. What is the computational power of "quantum" circuits, if we allow non-unitary (but still invertible) gates, and require the output to give the correct answer with certainty? This ...
0
votes
0answers
39 views

Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page ...
0
votes
1answer
98 views

PAC algorithms for APX-Hard problems

Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every ...
2
votes
1answer
135 views

Parallel (NC) replacements for Gaussian elimination?

Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine its rank, and a basis for its null-space. These can be computed ...
11
votes
1answer
270 views

$\mathsf{NP} \cap \mathsf{coNP}$ as oracle

Does $\mathsf{NP^{NP \,\cap\, coNP}=NP}$ hold? Clearly $\mathsf{NP^{NP}\neq NP}$, but it seems to me that $\mathsf{NP\cap coNP}$ is "deterministic" which makes me believe this is true. Is there a ...
16
votes
2answers
363 views

A good reference for complexity class operators?

I'm interested if there exist any good expository articles or surveys to which I can refer when I write about complexity class operators: operators which transform complexity classes by doing things ...
0
votes
0answers
135 views

Intermediate problems between nonuniform $NL$, $Mod_n L$ and $P$?

A related question asked about intermediate problems between $L$ and $NL$. I'm interested in problems between the nonuniform versions of $NL$, $Mod_n L$ and $P$. This makes sense as it is known that ...
2
votes
0answers
176 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means ...
11
votes
2answers
367 views

Is NP in $DTIME(n^{poly\log n})$?

Is NP in $DTIME(n^{poly\log n})$?
2
votes
2answers
149 views

Set packing with maximum coverage objective

We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$. Set-Packing asks how many disjoint sets we can pack, and is defined ...
0
votes
0answers
78 views

What kind of computations or algorithms give rise to iterated logarithm and inverse Ackermann function?

I heard a statement saying that iterated logarithm and inverse Ackermann function are usually the slowest growing functions used in computer program complexity analysis. Is that true? What kind of ...
1
vote
1answer
192 views

Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness: $EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness ...
7
votes
0answers
135 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
7
votes
0answers
138 views

Is the following “Occam's razor” decision problem a member of P?

While thinking about natural language processing, I came up with the following NP problem: OCCAM-k: Given a fixed natural number $k$, consider the following input: a natural number of states $S$ in ...
15
votes
1answer
251 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...
6
votes
1answer
142 views

Coding theory and complete problems

Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following: ...
15
votes
3answers
309 views

Complexity class separations without hierarchy theorems

Hierarchy theorems are fundamental tools. A good number of them was collected in an earlier question (see What hierarchies and/or hierarchy theorems do you know?). Some complexity class separations ...
5
votes
3answers
401 views

What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing ...
0
votes
1answer
96 views

Problems of similar complexity for different measures

It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a ...