<p>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. </p>

<p>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.</p>

<p>Reference: "An algorithm for finding Hamilton cycles in random graphs"</p>

<p>Bollobas, Fenner, Frieze</p>

<p><a href="http://portal.acm.org/citation.cfm?id=22145.22193">http://portal.acm.org/citation.cfm?id=22145.22193</a></p>

CC BY-SA 2.5
2010-08-24T15:04:25.923Z
2010-08-25T16:14:33.057Z
2010-08-25T16:14:33.057Z
Aaron Roth
<p>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.</p>

<p>Reference:</p>

<p>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. <a href="http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/6466595336e5d13885256f4a00715b9f?OpenDocument">Preprint</a></p>

CC BY-SA 2.5
2010-08-25T08:53:29.340Z
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
CC BY-SA 2.5
2010-08-25T14:57:27.853Z
@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
CC BY-SA 2.5
2010-08-26T13:07:06.750Z
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
CC BY-SA 2.5
2010-08-26T13:20:51.187Z
@Steve: I agree.
Serge Gaspers
CC BY-SA 2.5
2010-08-24T20:17:29.780Z
2010-08-25T16:26:11.910Z
2010-08-25T16:26:11.910Z
Serge Gaspers
<p>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.</p>

<p>Several lattice problems are known to have such worst-case to average-case reductions.  See, for instance, <a href="http://doi.acm.org/10.1145/237814.237838">Generating hard instances of lattice problems</a> by Ajtai, and a <a href="http://dx.doi.org/10.1007/978-3-642-02295-1_13">survey article</a> by Micciancio.</p>

CC BY-SA 2.5
2010-08-25T03:58:29.083Z
2010-08-25T03:58:29.083Z
Ian
<p>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</p>

<p>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: <a href="http://arxiv.org/abs/cs/0606037">http://arxiv.org/abs/cs/0606037</a>.</p>

CC BY-SA 2.5
2010-08-26T12:55:24.457Z
Thanks for the links.  Unfortunately the 3-SAT paper's "with high probability" results aren't strong enough (as far as I can see) to affirm my query.

I agree "sensible distribution" can be hairy.  In this, I would prefer it if the distribution isn't obviously chosen so that the "effective instance space" doesn't simply reduce the problem to one known to be in P.
Steve Kroon
CC BY-SA 2.5
2010-08-25T05:36:42.793Z
2010-08-25T05:36:42.793Z
Grigory Yaroslavtsev
<p><a href="https://doi.org/10.1007/3-540-36494-3_43" rel="nofollow noreferrer">&quot;Colouring Random Graphs in Expected Polynomial Time&quot; by
Amin Coja-Oghlan and Anusch Taraz</a></p>
<blockquote>
<p>We investigate the problem of colouring random graphs <span class="math-container">$G \in G(n, p)$</span> in polynomial expected time. For the case <span class="math-container">$p &lt; 1.01/n$</span>, 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 <span class="math-container">$O(√np)$</span>.</p>
</blockquote>

CC BY-SA 4.0
2010-08-24T15:26:16.513Z
2022-09-22T09:48:28.257Z
2022-09-22T09:48:28.257Z
Joel Rybicki
<p>A simple padding technique gives you a way to construct these from any problem.</p>

<hr>

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

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

CC BY-SA 3.0
2017-09-01T10:53:23.067Z
2017-09-01T10:53:23.067Z
Lieuwe Vinkhuijzen
<p>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)?</p>

<p>If not, are there problems for which the existence of such an algorithm has been established?</p>

<p>Or does the existence of such an algorithm imply the existence of a deterministic polynomial time algorithm?</p>

CC BY-SA 2.5
2010-08-24T15:52:46.297Z
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
CC BY-SA 2.5
2010-08-25T21:41:42.897Z
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ε
CC BY-SA 2.5
2010-08-26T06:31:36.830Z
@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
<cc.complexity-theory><np-hardness>
Are there NP-complete problems with polynomial expected time solutions?
Steve Kroon
# Are there NP-complete problems with polynomial expected time solutions?

(Asked by: username_0 on 2010-08-24)

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?

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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?  
> **username_0**: @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.  

---

## 6 answers

### Answer by username_9 on 2017-09-01. Score: 7 | Accepted answer

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 by username_3 on 2010-08-24. Score: 13

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 by username_6 on 2010-08-25. Score: 10

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](http://doi.acm.org/10.1145/237814.237838) by Ajtai, and a [survey article](http://dx.doi.org/10.1007/978-3-642-02295-1_13) by Micciancio.


---

### Answer by username_4 on 2010-08-24. Score: 9

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](http://domino.research.ibm.com/library/cyberdig.nsf/1e4115aea78b6e7c85256b360066f0d4/6466595336e5d13885256f4a00715b9f?OpenDocument)

> **Comments:**
> **username_5**: 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.  
> **username_4**: @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.  
> **username_0**: 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.  
> **username_4**: @Steve: I agree.  

---

### Answer by username_7 on 2010-08-25. Score: 7

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

> **Comments:**
> **username_0**: Thanks for the links.  Unfortunately the 3-SAT paper's "with high probability" results aren't strong enough (as far as I can see) to affirm my query.  I agree "sensible distribution" can be hairy.  In this, I would prefer it if the distribution isn't obviously chosen so that the "effective instance space" doesn't simply reduce the problem to one known to be in P.  

---

### Answer by username_8 on 2010-08-24. Score: 5

["Colouring Random Graphs in Expected Polynomial Time" by
Amin Coja-Oghlan and Anusch Taraz](https://doi.org/10.1007/3-540-36494-3_43)

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


---

