Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,576 questions
577 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 ...
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$ ...
1k 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 ...
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 ...
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 ...
3k views

What are the consequences of factoring being NP-complete?

Are there any references covering this?
714 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?
20k 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?
5k 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?
513 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 ...
489 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 ...
1k 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 ...
4k views

What are the best current lower bounds on 3SAT?

What are the best current lower bounds for time and circuit depth for 3SAT?
555 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?
444 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 ...
18k 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? ...
622 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 ...
1k 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 ...
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 ...
2k views

Consequences of Complete problems for NP intersects coNP

What are the consequences of having complete problems in $NP\cap coNP$?
4k views