patternMinor
Are there NP COMPLETE problems that are "easy" in practice?
Viewed 0 times
arepracticeproblemscompleteeasythatthere
Problem
NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of size $n$ for which the algorithm takes more than $p(n)$ time. But this is one instance for every (sufficiently large) $n$. In principle, this could be the only hard instance for that value of $n$, and all other instances for that $n$ could be easy. So how hard are NP COMPLETE problems in practice?
I'll refine that question to: Are there NP COMPLETE problems that are somehow easy in practice?
The definition of "easy" is left open. One definition may be given by average-case complexity, another one could be given "smooth complexity", another could be given by Fixed Parameter Tractability, efficient approximability, polynomial-time solvability with an advice oracle, efficiency in practice without a mathematical definition etc. I'm hoping that by leaving the definition of "easy" open, I can get a wider range of answers. Any definition of "easy" should imply that the problem is easy "in real life" or "in practice". Also, don't assume I know any of that stuff I just listed in any detail.
I'll refine that question to: Are there NP COMPLETE problems that are somehow easy in practice?
The definition of "easy" is left open. One definition may be given by average-case complexity, another one could be given "smooth complexity", another could be given by Fixed Parameter Tractability, efficient approximability, polynomial-time solvability with an advice oracle, efficiency in practice without a mathematical definition etc. I'm hoping that by leaving the definition of "easy" open, I can get a wider range of answers. Any definition of "easy" should imply that the problem is easy "in real life" or "in practice". Also, don't assume I know any of that stuff I just listed in any detail.
Solution
That a problem is NP-complete means just that the worst case is hard. It might well be that such worst cases are extremely rare, or just don't show up in the "usual" cases of interest, and that non-worst-cases instances are easy to solve.
To classify a problem as "usually easy" you'd have to specify the (distribution of the) inputs to consider, and check that the instances of interest are indeed (very often) easy. Both are very hard tasks, all you can do is to rely on avaliable experimental experience. Perhaps there are some NP-complete problems where it can be shown that all instances are equally hard, but I'm not aware of any.
For a somewhat off-topic example, the SIMPLEX algorithm is routinely used to solve huge linear programming problems. It turns out that the worst case of the algorithm is exponential --- but bad cases don't show up in practice, they seem to be extremely contorted.
To classify a problem as "usually easy" you'd have to specify the (distribution of the) inputs to consider, and check that the instances of interest are indeed (very often) easy. Both are very hard tasks, all you can do is to rely on avaliable experimental experience. Perhaps there are some NP-complete problems where it can be shown that all instances are equally hard, but I'm not aware of any.
For a somewhat off-topic example, the SIMPLEX algorithm is routinely used to solve huge linear programming problems. It turns out that the worst case of the algorithm is exponential --- but bad cases don't show up in practice, they seem to be extremely contorted.
Context
StackExchange Computer Science Q#103776, answer score: 4
Revisions (0)
No revisions yet.