Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,955
questions
5
votes
1
answer
441
views
High probable polynomial time algorithm for NP-hard problems?
Many NP-complete or NP-hard problems are addressed under the assumption that the problem instances are uniformly distributed. However, it is not true for real world applications. One example is the ...
- 161
38
votes
3
answers
4k
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 ...
- 383
25
votes
2
answers
1k
views
Is "Experimental Complexity Theory" being used to solve open problems?
Scott Aaronson proposed an interesting challange: can we use supercomputers today to help solve CS problems in the same way that physicists use large particle colliders?
More concretely, my ...
- 2,233
1
vote
3
answers
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 ...
- 20.7k
4
votes
4
answers
493
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 ...
- 20.7k
7
votes
4
answers
425
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$.
- 341
28
votes
6
answers
3k
views
Are there NP-complete problems with polynomial expected time solutions?
Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?
If not, are there problems for ...
- 383
4
votes
1
answer
227
views
Unique games conjecture - edge permutations
What do the edge permuations in the unique games conjecture represent?
- 475
10
votes
0
answers
355
views
Collapsing of exptime and alternation bounded turing machine
This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)
Let C be a ...
- 1,521
10
votes
1
answer
402
views
Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?
By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice,
and the derandomization should give us, say, a P/linear or (SUBEXP/linear) ...
29
votes
0
answers
1k
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\...
4
votes
4
answers
4k
views
Why is P vs. NP so hard? [closed]
Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?
Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?
Why is it so hard?
All I'm looking for is the hindrances ...
- 175
9
votes
6
answers
632
views
Reducing complexity with parallelism
Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?...
- 253
14
votes
2
answers
1k
views
Space alternating hierarchy
It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions).
In the same paper, Immerman state that the ...
- 1,521
49
votes
8
answers
8k
views
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
- 21.3k
0
votes
0
answers
449
views
Complexity Theory conferences? [closed]
What are the most significant annual Complexity Theory conferences?
Rules:
One conference per answer
Include a link to the conference
11
votes
3
answers
740
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 ...
- 5,026
12
votes
3
answers
679
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 $...
- 3,280
19
votes
4
answers
1k
views
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
- 1,023
17
votes
4
answers
398
views
Alternate notion of complexity based on gap between brute-force and the best algorithm?
Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a ...
- 2,707
28
votes
3
answers
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 ...
- 36.3k
11
votes
3
answers
613
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?
(...
- 36.3k
34
votes
5
answers
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 "...
- 9,820
45
votes
10
answers
4k
views
Kolmogorov complexity applications in computational complexity
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
16
votes
2
answers
2k
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 ...
- 398
37
votes
9
answers
2k
views
Surprising Results in Complexity (Not on the Complexity Blog List)
What were the most surprising results in complexity?
I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of ...
14
votes
3
answers
604
views
How hard is it to reduce termination to partial correctness?
If you are familiar with program verification you are likely to prefer reading the Question before the Background. If you are not familiar with program verification then you may still be able to ...
- 4,776
20
votes
1
answer
433
views
Explain Gurvits's tensor-rank interpretation of Deolalikar's paper
[Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]
On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent ...
- 36.3k
18
votes
2
answers
831
views
Lower bounds on Gaussian complexity
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity ...
- 1,704
18
votes
1
answer
774
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 ...
- 8,871
29
votes
4
answers
2k
views
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.
Example: the case $k = 4$ ...
- 11.4k
37
votes
3
answers
2k
views
Parameterized complexity of Hitting Set in finite VC-dimension
I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and ...
- 2,583
29
votes
2
answers
2k
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 ...
- 8,871
22
votes
2
answers
1k
views
How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?
The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about ...
- 2,025
30
votes
2
answers
6k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 793
15
votes
3
answers
913
views
Can it be determined if language L lies in NP?
Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
- 793
14
votes
1
answer
38k
views
Is integer factorization an NP-complete problem? [duplicate]
Possible Duplicate:
What are the consequences of factoring being NP-complete?
What notable reference works have covered this?
- 793
42
votes
7
answers
6k
views
Many-one reductions vs. Turing reductions to define NPC
Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
- 1,648
22
votes
2
answers
587
views
Lower bounds for constant-depth formulae?
We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known ...
- 13.4k
21
votes
3
answers
541
views
Are recursive forms of Godel's statement possible?
The self-referentiality of the P/NP problem has sometimes been highlighted as a barrier to its resolution, see, for instance, Scott Aaronson's paper, is P vs. NP formally independent? One of the many ...
- 853
36
votes
5
answers
2k
views
Complexity of testing for a value versus computing a function
In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example:
Evaluating the ...
- 36.3k
51
votes
4
answers
5k
views
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
- 13.5k
24
votes
2
answers
868
views
What evidence do we have for (and against) Unique Games Conjecture?
Subhash Khot's Unique Games Conjecture is one of active research areas in complexity theory.
What evidence do we have for it? What evidence do we have against it?
21
votes
4
answers
495
views
Which results in complexity theory make essential use of uniformity?
A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like ...
- 21.3k
141
votes
30
answers
24k
views
Problems Between P and NPC
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
17
votes
2
answers
682
views
H-free cut problem
Suppose you are given a connected, simple, undirected graph H.
The H-free cut problem is defined as follows:
Given a simple, undirected graph G, is
there a cut (partition of vertices
into two ...
- 1,855
27
votes
4
answers
2k
views
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
- 18.8k
30
votes
2
answers
2k
views
Hierarchies in NP (under the assumption that P != NP)
Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.
Is there any evidence of more ...
- 1,855
26
votes
1
answer
2k
views
Consequences of Complete problems for NP intersects coNP
What are the consequences of having complete problems in $NP\cap coNP$?
- 3,280
65
votes
11
answers
5k
views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
- 1,459