Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity-classes]

Computational complexity classes and their relations

4
votes
3answers
494 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
426 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 ...
16
votes
2answers
1k 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 ...
19
votes
1answer
746 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
274 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
196 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.
36
votes
3answers
2k 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
982 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
432 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
388 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
872 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
498 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
502 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 $...
26
votes
3answers
903 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
546 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? (...
31
votes
5answers
1k 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 "...
14
votes
2answers
709 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
548 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 ...