<p>This 1989 article by Dyer and Frieze answers the question directly:</p>
<p><a href="https://www.math.cmu.edu/users/af1p/Texfiles/SOLUTSOMERAND.pdf" rel="nofollow noreferrer">The Solution of Some Random NP-hard Problems in Polynomial Expected Time</a>.</p>

CC BY-SA 4.0
2022-07-23T20:40:50.050Z
Excellent! Glad you could answer your own question :)
J.y B.y
CC BY-SA 4.0
2022-07-22T20:27:58.763Z
2022-07-23T20:40:10.007Z
2022-07-23T20:40:10.007Z
Kolja
<p>That is a good question :)
As mentioned in the comments, <em>there are various decision problems which are NP-Hard (worst case complexity) while easy on average (average case complexity), <strong>for some distribution of instances</strong>!</em></p>
<p><strong>THEORETICAL EXPLANATION:</strong></p>
<p>The NP-Hardness concept is one of <strong>worst case complexity</strong>. Simplifying a bit, by definition a &quot;Non-deterministic Polynomial time (NP)&quot; algorithm which &quot;decides&quot; a NP Hard decision problem can be seen as a decision tree with an exponential fan-out (which is unavoidable unless P=NP) and a height (length of the longest branch) polynomial in the length of the input, where various instances lead to various leaves of such tree.</p>
<p>In most natural problems, most of the branches of this tree do not give an answer, forcing the algorithm to explore all the branches, which yield a running time exponential in the length of the input. But for some version of some problems (I give an example based on the parameterized version of the SATisfiability problem below), a constant fraction (e.g. half) of the branches yield a certified answer, which means that 1) a randomized algorithm has a constant probability to discover such branch (e.g. 1/2), and an expected running time corresponding to the traversal of a constant number of branches (e.g. within <span class="math-container">$O(1)$</span>) instead of an exponential one; and 2) a deterministic algorithm running on a uniform distribution of instances will have a polynomial running time on average.</p>
<p>More generally, while many algorithms for NP Hard problem do not have a constant fraction of their branches leading to a useful certificate of the instance, if one 1) restricts the set of allowed instances and/or 2) skews the distribution of the instances so that to increase the probability to reach a usable certificate, the average complexity can become substantially smaller than the worst case complexity.</p>
<p><strong>CONCRETE EXAMPLE:</strong></p>
<p>Concrete examples have been quite well documented by researchers working on the <em>phase transition</em> of the <em>SATisfiability decision problem</em>. Again, simplifying (more than) a bit,  the <em>SATisfiability decision problem</em> is NP-Hard, but some observed that for some ranges of values of the ratio between the number of clauses and the number of variables, there are many value assignments to the variables which satisfy the formula, making such instances easy for randomized algorithms, or the average complexity of deterministic algorithms polynomial on average on such instances.</p>
<p>I did not know a good survey of such phase transition results, but this <a href="https://www.sciencedirect.com/science/article/pii/S0378437109010656" rel="nofollow noreferrer">2010 article</a> seems to give a good overview, should you want to go beyond what I could summarize in a Stack Exchange post!</p>
<p>I hope it helps, take care!</p>

CC BY-SA 4.0
2022-07-21T10:50:58.003Z
2022-07-21T10:50:58.003Z
J.y B.y
<p>I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an algorithm.</p>
<p>Are there NP-hard (NP-complete) problems which are easy on average?</p>

CC BY-SA 4.0
2022-07-21T03:37:59.743Z
Depending on the distribution over instances, many. For example, Hamiltonian circuit in a random graph where every edge exists with extremely high probability (but not probability one) will be easy on average,, but hard in the worst case.
usul
CC BY-SA 4.0
2022-07-21T11:33:40.233Z
It’s easy to construct such problems artificially. E.g., define a language $L$ such that an $n$-bit string is in $L$ iff its leftmost $n/2$ bits encode a satisfiable CNF, and the remaining bits are all $0$. Then $L$ is NP-complete by an obvious reduction from SAT, but it is trivial to compute on average, as the answer is NO for all but a $2^{-n/2}$ fraction of $n$-bit inputs.
Emil Jeřábek
CC BY-SA 4.0
2022-07-22T17:55:55.800Z
A bit more interesting version of these comments could be a distribution on graphs where the [treewidth](https://en.wikipedia.org/wiki/Treewidth) is bounded by a constant with high probability.
usul
<np-hardness><average-case-complexity>
NP-hard problem which is easy on average
Kolja
# NP-hard problem which is easy on average

(Asked by: username_0 on 2022-07-21)

I have a feeling like I read somewhere that the Hamiltonian circuit problem is NP-hard, but it is easy on average, or easy for a random instance. However, I cannot find a reference for that, nor an algorithm.

Are there NP-hard (NP-complete) problems which are easy on average?

**Tags:** np-hardness, average-case-complexity

> **Comments:**
> **username_1**: Depending on the distribution over instances, many. For example, Hamiltonian circuit in a random graph where every edge exists with extremely high probability (but not probability one) will be easy on average,, but hard in the worst case.  
> **username_2**: It’s easy to construct such problems artificially. E.g., define a language $L$ such that an $n$-bit string is in $L$ iff its leftmost $n/2$ bits encode a satisfiable CNF, and the remaining bits are all $0$. Then $L$ is NP-complete by an obvious reduction from SAT, but it is trivial to compute on average, as the answer is NO for all but a $2^{-n/2}$ fraction of $n$-bit inputs.  
> **username_1**: A bit more interesting version of these comments could be a distribution on graphs where the [treewidth](https://en.wikipedia.org/wiki/Treewidth) is bounded by a constant with high probability.  

---

## 2 answers

### Answer by username_0 on 2022-07-22. Score: 4 | Accepted answer

This 1989 article by Dyer and Frieze answers the question directly:

[The Solution of Some Random NP-hard Problems in Polynomial Expected Time](https://www.math.cmu.edu/users/af1p/Texfiles/SOLUTSOMERAND.pdf).

> **Comments:**
> **username_3**: Excellent! Glad you could answer your own question :)  

---

### Answer by username_3 on 2022-07-21. Score: 3

That is a good question :)
As mentioned in the comments, *there are various decision problems which are NP-Hard (worst case complexity) while easy on average (average case complexity), **for some distribution of instances**!*

**THEORETICAL EXPLANATION:**

The NP-Hardness concept is one of **worst case complexity**. Simplifying a bit, by definition a "Non-deterministic Polynomial time (NP)" algorithm which "decides" a NP Hard decision problem can be seen as a decision tree with an exponential fan-out (which is unavoidable unless P=NP) and a height (length of the longest branch) polynomial in the length of the input, where various instances lead to various leaves of such tree.

In most natural problems, most of the branches of this tree do not give an answer, forcing the algorithm to explore all the branches, which yield a running time exponential in the length of the input. But for some version of some problems (I give an example based on the parameterized version of the SATisfiability problem below), a constant fraction (e.g. half) of the branches yield a certified answer, which means that 1) a randomized algorithm has a constant probability to discover such branch (e.g. 1/2), and an expected running time corresponding to the traversal of a constant number of branches (e.g. within $O(1)$) instead of an exponential one; and 2) a deterministic algorithm running on a uniform distribution of instances will have a polynomial running time on average.

More generally, while many algorithms for NP Hard problem do not have a constant fraction of their branches leading to a useful certificate of the instance, if one 1) restricts the set of allowed instances and/or 2) skews the distribution of the instances so that to increase the probability to reach a usable certificate, the average complexity can become substantially smaller than the worst case complexity.

**CONCRETE EXAMPLE:**

Concrete examples have been quite well documented by researchers working on the *phase transition* of the *SATisfiability decision problem*. Again, simplifying (more than) a bit, the *SATisfiability decision problem* is NP-Hard, but some observed that for some ranges of values of the ratio between the number of clauses and the number of variables, there are many value assignments to the variables which satisfy the formula, making such instances easy for randomized algorithms, or the average complexity of deterministic algorithms polynomial on average on such instances.

I did not know a good survey of such phase transition results, but this [2010 article](https://www.sciencedirect.com/science/article/pii/S0378437109010656) seems to give a good overview, should you want to go beyond what I could summarize in a Stack Exchange post!

I hope it helps, take care!


---

