Questions tagged [complexity-classes]

Computational complexity classes and their relations

Filter by
Sorted by
Tagged with
25
votes
4answers
2k views

Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...
24
votes
3answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
13
votes
1answer
490 views

Why are these two definitions of PPAD equivalent?

The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete. End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-...
12
votes
2answers
1k views

Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
6
votes
1answer
1k views

Is #P contained in PSPACE?

It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE? It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and ...
26
votes
3answers
2k views

Consequences of #P = FP

Which would be the consequences of #P = FP? I'm interested in both practical and theoretical consequences. From a practical point of view, I'm particularly interested in consequences on Artificial ...
21
votes
3answers
895 views

Limits to Parallel Computing

I am curious in a broad sense about what is known about parallelizing algorithms in P. I found the following wikipedia article about the subject: http://en.wikipedia.org/wiki/NC_%28complexity%29 The ...
1
vote
1answer
250 views

Is the problem of finding the “all-terminal connectivity polynomial” polynomially bounded?

I want to proof whether the problem of finding the "all-terminal connectivity polynomial" of a given graph G(V,E) is checkable in a polynomial time. In order to do so I should first proof that it is ...
5
votes
1answer
279 views

What is the size of a function?

I'm not sure whether this question should be asked on mathoverflow.com or here, but as it is in the context of computational complexity, I will ask here. Context Oded Goldreich states in his book ...
12
votes
3answers
265 views

Is there a natural restriction of VO logic which captures P or NP?

The paper Lauri Hella and José María Turull-Torres, Computing queries with higher-order logics, TCS 355 197–214, 2006. doi: 10.1016/j.tcs.2006.01.009 proposes logic VO, variable-order logic. This ...
4
votes
0answers
688 views

Is Witten's new method of quantization useful for geometric complexity theory? [closed]

The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
3
votes
2answers
306 views

Complexity Classes - separations and inclusions [closed]

What are the basic complexity class seperation and inclusion results that everybody should know? (I mean specifically results that are known, and the proofs can be understood by a non-expert) It ...
10
votes
3answers
473 views

Which algorithms can be expressed using a total functional language with data parallel operators?

Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are ...
7
votes
1answer
389 views

Cobham's Result on Efficient Computations

In the following paper: Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland. Cobham defined the class P ...
10
votes
1answer
426 views

Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.
10
votes
2answers
308 views

Is there known any complexity class containing online counterparts of optimization problems?

Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined? We know that many problems have their online version: e.g. ...
1
vote
1answer
242 views

Unary languages in $AC^0$?

Barrington, Immerman, and Straubing state circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$) I'd ...
8
votes
3answers
1k views

Relationship between SPACE(n) and E

Is it known whether SPACE(n) (the class of languages recognized by deterministic TMs with linear space) is a proper subset of E (the class of languages recognized by deterministic TMs in time 2^O(n))?
10
votes
1answer
424 views

What are the complexities of the following SAT subsets ?

Assume $P \neq NP$ Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$). |x| is the size of the instance x. Let L be ...
7
votes
1answer
909 views

Oracle relative to which BPP = EXP

An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could ...
10
votes
5answers
901 views

Complexity Classes for Cases Other Than “Worst Case”

Do we have complexity classes with respect to, say, average-case complexity? For instance, is there a (named) complexity class for problems which take expected polynomial time to decide? Another ...
22
votes
3answers
966 views

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
16
votes
1answer
770 views

LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free ...
8
votes
1answer
2k views

Reducing #SAT to #MONOTONE-2SAT

The problem #MONOTONE-2SAT is known to be #P-complete. This means that #SAT can be reduced to it. My question is: given a #SAT instance $F$, which is the transformation that converts $F$ to its ...
38
votes
2answers
3k views

Semantic vs. Syntactic Complexity Classes

In his "Computational Complexity" book, Papadimitriou writes: RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
7
votes
2answers
421 views

On the class of the FNP version of the Hamiltonian Cycle problem

This post is linked to: FNP complexity class Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in ...
4
votes
3answers
532 views

FNP complexity class

Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity) However, that isn't sufficient for me to ...
5
votes
1answer
435 views

Comparing $\mathbf{NP}$ and $\mathbf{E}$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$. The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
17
votes
2answers
2k views

Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

In the "last paragraph" of the "first page" of the following paper: Vikraman Arvind, Johannes Köbler, Uwe Schöning, Rainer Schuler, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical ...
21
votes
1answer
892 views

Do all complexity classes have a leaf language characterization?

Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a ...
18
votes
1answer
1k views

Cutting-sticks puzzle

Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2. Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time? ...
5
votes
1answer
277 views

Are there known “completion” operations over languages ?

Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$. Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$. Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) ...
3
votes
1answer
210 views

Sparsity of Horn satisfiability?

Is the set of satisfiable Horn formulas sparse? A sparse language contains a polynomially bounded number of srings at every length.
37
votes
3answers
3k views

Does $VP \neq VNP$ imply $P \neq NP$?

As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
1
vote
3answers
1k views

PCP characterization of NP

The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any ...
4
votes
4answers
444 views

Are there alternatives to using polynomials in defining the different notions of efficient computation?

Is invoking polynomials in defining the different notions of efficient computation the real obstacle to resolve the P vs NP problem? Do we need a paradigm shift by redefining what constitute an ...
7
votes
4answers
406 views

Complexity class separation in the presence of relativization barriers

Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that 1. $M^A=N^A$ and 2. $M^B\neq N^B$ and 3. $M \neq N$.
29
votes
0answers
985 views

Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?

By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary. I think this is a proof: if $EXP\...
10
votes
3answers
635 views

What evidence is there that $coRP \neq NP$?

What evidence is there that $coRP \neq NP$? $coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input ...
12
votes
3answers
588 views

$NP\cap coAM$ Languages

What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references? Update: I forgot to mention that I'm interested in languages not known to be in $...
28
votes
3answers
1k views

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$? Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of ...
11
votes
3answers
601 views

Two Variants of NP

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes? (...
32
votes
5answers
2k views

Evidence that PPAD is hard?

There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be "...
16
votes
2answers
1k views

Is APX contained in NP?

A problem P is said to be in APX if there exists some constant c > 0 such that a polynomial-time approximation algorithm exists for P with approximation factor 1 + c. APX contains PTAS (seen by ...
18
votes
1answer
675 views

Best known joint containments for/by NP and Parity-P?

Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...
27
votes
2answers
1k views

What are the consequences of Parity-L = P?

Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...

1
8 9 10 11
12