4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – usul
    Jul 21, 2022 at 3:37
  • 6
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Jul 21, 2022 at 11:33
  • 1
    $\begingroup$ A bit more interesting version of these comments could be a distribution on graphs where the treewidth is bounded by a constant with high probability. $\endgroup$
    – usul
    Jul 22, 2022 at 17:55

2 Answers 2

Reset to default
4
$\begingroup$

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

The Solution of Some Random NP-hard Problems in Polynomial Expected Time.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Excellent! Glad you could answer your own question :) $\endgroup$
    – J..y B..y
    Jul 23, 2022 at 20:40
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.