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 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?

• I don't quite understand what the question is. Are you asking for average-case results for NP-hard problems or are you asking whether we can solve NP-hard problems in the worst-case in expected polynomial time? – Moritz Aug 24 '10 at 15:52
• What do you mean by "expected running time"? Are you taking the expectation over some random distribution of inputs (as most of the answers seem to think), or over the distribution of random bits used by the algorithm (the usual meaning for randomized algorithms), or both? – Jeffε Aug 25 '10 at 21:41
• @Moritz: I'm asking about average-case results for NP-hard problems. Solving NP-hard problems in the worst-case in expected polynomial time seems like an even stronger result to me, so I'd be interested in such results as well. @JeffE I'm talking about expected time w.r.t. some distribution over the instances. If the algorithm is randomized, one would take the expectation over the random bits as well. But my question is not primarily about randomized algorithm. – Steve Kroon Aug 26 '10 at 6:31

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$$

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

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.

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

• I don't see how your statement matches the claims in the paper. The paper talks about solving Max 2-CSP if the underlying graph is a random graph in the G(n,c/n) model for some fixed c, which means that it's a graph on n vertices where each edge occurs independently with probability c/n, hence in expectation there are $\Theta(n)$ edges (constraints) in the instance. But if you do NP-hardness reductions to get hard instances with n vertices and n edges, the distribution of instances will NOT follow the $G(n,c/n)$ model and hence I would not say that the paper solves an NP-hard problem. – Bart Jansen Aug 25 '10 at 8:53
• @Bart: I might have misunderstood the question. I claim that Max 2-CSP with a linear number of clauses is NP-hard, but that there exists an algorithm with expected linear time solving this problem for random instances. – Serge Gaspers Aug 25 '10 at 14:57
• Basically, if I understand your argument correctly, you're saying that Max 2-CSP equipped with the distribution G(n, c/n) over the underlying graphs can be solved in expected linear time. I do agree with Bart in that the distribution does not seem entirely "sensible" or "natural" to me, but I think it answers my question adequately. – Steve Kroon Aug 26 '10 at 13:07
• @Steve: I agree. – Serge Gaspers Aug 26 '10 at 13:20

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

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)$.