Are there NP-complete problems with polynomial expected time solutions?

Question

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 which the existence of such an algorithm has been established?

Or does the existence of such an algorithm imply the existence of a deterministic polynomial time algorithm?

Answer 1

There is a polynomial time algorithm for finding Hamiltonian cycles on random graphs, that succeeds asymptotically with the same probability that a Hamiltonian cycle exists. Of course, this problem is NP-hard in the worst case.

They also show that a dynamic programming algorithm which is always guaranteed to find a Hamiltonian cycle, if it exists, has polynomial expected running time, if the input distribution is uniformly random over the set of all $n$ vertex graphs.

Reference: "An algorithm for finding Hamilton cycles in random graphs"

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193

Answer 2

Regarding your last question on whether the existence of a good average case algorithm would imply the existence of a good worst-case algorithm: this is a major open question that is particularly of interest to cryptographers. Cryptography requires problems that are hard on average, but cryptographers would like to base their constructions on the minimum assumptions possible, so it is of great interest to find problems where the average-case hardness is provably equal to the worst-case hardness.

Several lattice problems are known to have such worst-case to average-case reductions. See, for instance, Generating hard instances of lattice problems by Ajtai, and a survey article by Micciancio.

Answer 3

Basically, Max 2-CSP on $n$ variables and $n$ randomly chosen constraints can be solved in expected linear time (see the reference below for the exact formulation of the result). Note that Max 2-CSP remains NP-hard when the number of clauses equals the number of variables as it is NP-hard if the constraint graph of the instance has maximum degree at most 3 and you can add some dummy variables to decrease the average degree to 2.

Reference:

Alexander D. Scott and Gregory B. Sorkin. Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time. Comb. Probab. Comput., 15(1-2):281-315, 2006. Preprint

Answer 4

A simple padding technique gives you a way to construct these from any problem.

---

Suppose $L$ is an $NP$-Complete language which requires $O(2^{n})$ time to solve. Then let $K$ be $$K=\{1^nx\ |\ \|x\|=n \text{ and }x\in L\}$$ Then $K$ is solved as follows: a linear-time algorithm checks whether an input string has an even number of characters of which the first $n$ are $1^n$. If not, it rejects; otherwise it solves $x\overset{?}{\in}L$. If $y\in_R \{0,1\}^{2n}$ is drawn uniformly at random, the expected time to solve $y\overset{?}{\in}K$ is $$\frac{1}{2^{2n}}\big(2^n\cdot 2^n+(2^{2n}-2^n)O(n)\big) = 1+(1-\frac{1}{2^n})O(n)\in O(n).$$

$K$ is $NP$-Complete. A reduction from $L$ is: $$x\in \{0,1\}^n \mapsto 1^nx$$

Answer 5

This doesn't answer your question completely, but for survey of results on random instances of 3-SAT you can see this: www.math.cmu.edu/~adf/research/rand-sat-algs.pdf

Usually it is difficult to define what "sensible distrubution" really means. You can follow this link to read more about this in survey "Average-time complexity" by Bogdanov and Trevisan: http://arxiv.org/abs/cs/0606037.

Answer 6

"Colouring Random Graphs in Expected Polynomial Time" by Amin Coja-Oghlan and Anusch Taraz

We investigate the problem of colouring random graphs $G \in G(n, p)$ in polynomial expected time. For the case $p < 1.01/n$, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of $O(√np)$.