Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
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? ...
72 votes
8 answers
10k 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 ...
  • 1,496
48 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 ...
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$) ...
51 votes
20 answers
8k 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 ...
91 votes
14 answers
20k 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,741
49 votes
9 answers
10k 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.4k
46 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-...
40 votes
2 answers
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 ...
  • 16.4k
36 votes
5 answers
8k 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 ...
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?
41 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$, ...
  • 411
26 votes
4 answers
2k 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 ...
41 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,638
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 ...
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.3k
19 votes
1 answer
590 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.3k
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
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 ...
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 ...
28 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 ...
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 "...
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
34 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,400
30 votes
7 answers
2k 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 ...
30 votes
2 answers
6k views

What would be the consequences of factoring being NP-complete?

Are there any references covering this?
17 votes
2 answers
701 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 ...
16 votes
2 answers
2k views

Is NP in $DTIME(n^{poly\log n})$?

Is NP in $DTIME(n^{poly\log n})$?
's user avatar
22 votes
1 answer
849 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 ...
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 ...
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,950
8 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. ...
  • 10.9k
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 ...
37 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 ...
38 votes
4 answers
6k 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,503
30 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 ...
29 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.3k
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 ...
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
37 votes
3 answers
2k 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. ...
  • 371
29 votes
2 answers
1k 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,708
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 ...
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,213
23 votes
1 answer
972 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 ...
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
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
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
18 votes
3 answers
983 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 ...
57 votes
9 answers
24k views

Explain P = NP problem to 10 year old

It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it? ...
70 votes
7 answers
4k views

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...

1
2 3 4 5
12