Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
620
questions
141
votes
30
answers
25k
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? ...
73
votes
9
answers
11k
views
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input ...
- 1,506
47
votes
3
answers
5k
views
An NP-complete variant of factoring.
Arora and Barak's book presents factoring as the following problem:
$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$
They add, further ...
- 3,946
36
votes
2
answers
5k
views
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
- 20.8k
52
votes
20
answers
9k
views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
- 10.6k
93
votes
14
answers
21k
views
What kind of mathematical background is needed for complexity theory?
I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
- 3,751
51
votes
9
answers
11k
views
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
- 16.5k
41
votes
2
answers
4k
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 ...
- 16.5k
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.6k
48
votes
4
answers
4k
views
Generalized Ladner's Theorem
Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
- 18.9k
37
votes
5
answers
9k
views
NEXP-complete problems
There are tons of NP-complete problems around and sources collecting them, e.g. see the book by Garey and Johnson. I would be interested to see a list of NEXP-complete problems as well. Is there one ...
42
votes
2
answers
2k
views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
- 421
43
votes
7
answers
7k
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,658
43
votes
3
answers
4k
views
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
- 21.5k
33
votes
5
answers
2k
views
Programming languages for efficient computation
It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard ...
- 10.2k
28
votes
2
answers
1k
views
Finding a prime greater than a given bound
Is a deterministic polynomial-time algorithm known for the following problem:
Input: a natural number $n$ (in binary encoding)
Output: a prime number $p > n$.
(According to a list of open ...
- 751
25
votes
4
answers
3k
views
Proofs, Barriers and P vs NP
It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into ...
- 10.6k
21
votes
2
answers
2k
views
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
- 6,970
19
votes
1
answer
689
views
Looking for a nice problem inside SC but not in the first two levels
The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{...
- 21.5k
65
votes
5
answers
2k
views
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
- 13.5k
55
votes
2
answers
4k
views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "...
- 18.9k
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
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 ...
35
votes
2
answers
3k
views
NTIME(n^k) ≠ DTIME(n^k) ?
In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.
...
- 4,439
31
votes
2
answers
7k
views
What would be the consequences of factoring being NP-complete?
Are there any references covering this?
- 803
31
votes
3
answers
2k
views
Justification of log f in DTIME hierarchy theorem
If we look at DTIME hierarchy theorem, we've got a log due to the overhead in simulation of a deterministic Turing Machine by a universal machine :
$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$
We ...
- 1,743
29
votes
6
answers
2k
views
Which SAT problems are easy?
What are "easy regions" for satisfiability? In other words, sufficient conditions for some SAT solver to be able to find a satisfying assignment, assuming it exists.
One example is when each clause ...
- 4,681
29
votes
7
answers
3k
views
Proving lower bounds by proving upper bounds
The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to ...
- 20.8k
22
votes
1
answer
864
views
How much computational power fits into a cubic centimeter?
This question is a followup on the question about DNA algorithms asked by Aadita Mehra.
In comments there, Joe Fitzsimmons said, in part:
[T]he radius of the system must scale proportionately to ...
- 6,994
20
votes
1
answer
1k
views
Consequences of UP equals NP
EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic ...
- 7,638
20
votes
4
answers
3k
views
Computational complexity in quantitative finance
Predicting the stock market is hard! Can TCS make this sentiment more formal?
Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge ...
- 10.2k
17
votes
2
answers
2k
views
17
votes
2
answers
737
views
Hardness of parameterized CLIQUE?
Let $0\le p\le 1$ and consider the decision problem
CLIQUE$_p$
Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
Question: does $G$ contain a clique on at ...
- 18.9k
9
votes
2
answers
1k
views
(0,1)-vector XOR problem
this is a rewrite of another recent question of mine [1] that wasnt stated well (it had a semi obvious simplification, mea culpa) but I think theres still a nontrivial question at the heart of it. ...
- 11k
50
votes
5
answers
7k
views
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
- 1,259
40
votes
4
answers
7k
views
Is $PH \subseteq PP$?
We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$.
Do we know whether $...
- 4,788
38
votes
3
answers
3k
views
Complexity of exponential function
We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.
...
- 381
38
votes
4
answers
2k
views
Interactive proofs for levels of the polynomial hierarchy
We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want ...
- 24.3k
33
votes
2
answers
2k
views
When does "X is NP-complete" imply "#X is #P-complete"?
Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.
Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?
Of course the existence ...
- 4,258
30
votes
3
answers
2k
views
A decision problem which is not known to be in PH but will be in P if P=NP
Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not ...
- 16.4k
30
votes
2
answers
2k
views
Derandomizing Valiant-Vazirani?
The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
- 3,748
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
23
votes
2
answers
1k
views
Relationship between symmetry and computational intractability?
The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.
However, If $k(n)=O(\log n)$...
- 20.8k
23
votes
1
answer
1k
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 ...
- 13.5k
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,035
21
votes
4
answers
2k
views
DNA-algorithms and NP-completeness
What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
- 283
19
votes
4
answers
3k
views
What is the "right" definition of upper and lower bounds?
Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.
So, what is the lower ...
- 331
19
votes
5
answers
3k
views
Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?
It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$.
This can easily be understood inductively using oracle machines.
The question ...
- 387
18
votes
3
answers
1k
views
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
- 10.2k
12
votes
2
answers
2k
views
Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?
By http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf
If $A$ is a PSPACE-complete language, $P^{A}=NP^{A}$.
If $B$ is a deterministic polynomial-time oracle, $P^{B}\ne NP^{B}$ (assuming $P\...
- 709