Computational complexity classes and their relations

learn more… | top users | synonyms

-4
votes
0answers
31 views

Oracle reduction to 3SAT [on hold]

Show that there is an oracle A and a language L\in NP^A (NP TM with access to oracle A) such that L is not polynomial time reducible to 3SAT even when the machine computing the reduction is allowed ...
1
vote
0answers
146 views

Determine the complexity class of a language [closed]

Let $L'$ be the language containing all the pairs $(G,v)$ where $G$ is a directed graph and $v$ is a vertex in $G$ such that $G$ contains a cycle (i.e. closed walk) that contains $v$ and the number of ...
10
votes
2answers
247 views

Minimum Tree-width of circuit for MAJORITY

What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ? Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$. I care ...
13
votes
0answers
171 views

What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows. Is there a result comparable to the ...
-1
votes
0answers
63 views

Is this construction of large monotone boolean formulas in Exp or PSpace?

For every boolean formula $P$ on $N$ variables there exists a monotone formula $Q$ on $N$ variables that decides all QBFs of $P$ (QBFs are decided by evaluating assignments to $Q$). The formula $Q$ ...
18
votes
1answer
459 views

Is P equal to the intersection of all superpolynomial time classes?

Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$. It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf ...
6
votes
0answers
467 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
4
votes
0answers
210 views

Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
1
vote
1answer
229 views

#P-complete problems are at least as hard as NP-complete problems

I just read J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983) and one of the first ...
12
votes
1answer
207 views

Large classes which contain LOGSPACE for which strict inclusions are unknown

The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references). Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
0
votes
0answers
123 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
122 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
678 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 ...
4
votes
1answer
372 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
130 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
70 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
409 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 ...
5
votes
3answers
294 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
126 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
85 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
157 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
219 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
109 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
358 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
297 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
58 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
122 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
128 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
449 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
202 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
199 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 ...
27
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
254 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
135 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
187 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
49 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 ...
33
votes
4answers
993 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
223 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
233 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
124 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
140 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 ...
12
votes
1answer
279 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
372 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
182 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
383 views

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

Is NP in $DTIME(n^{poly\log n})$?
2
votes
2answers
150 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 ...