6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You already seem to know that not every instance of an NPC problem is hard. So what's the question, really? SAT has been heavily studied and you will have no problem finding "real instances" that are easy in practice. $\endgroup$
    – Juho
    Commented Feb 3, 2019 at 0:23

4 Answers 4

Reset to default
11
$\begingroup$

Honestly, SAT seems pretty easy in practice. SAT solvers are routinely used on instances with millions of variables that arise in model checking against formal specifications.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

Problems which are easy to approximate, like the Euclidean Traveling Salesman problem.

These are problems for which polynomial-time approximation scheme (PTAS) approximation algorithm do exist.

A PTAS is an algorithm which takes an instance of an optimization problem and a parameter ε > 0 and produces a solution that is within a factor 1 + ε of being optimal (or 1 – ε for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most (1 + ε)L, with L being the length of the shortest tour.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It should also be noticed that problems with an FPTAS (fully polytime approx scheme), like the knapsack problem, are even easier. $\endgroup$
    – Erotemic
    Commented May 3, 2023 at 16:50
3
$\begingroup$

See this question: A greedy algorithm for the bottle filling problem

I added a proof that this problem is NP-complete. However, practical instances of the problem will usually be quite easy to solve; the proof transformed the knapsack problem into highly unusual instances of this problem.

PS. Why is this problem usually easy? Look at the link where the problem is described, and what people think of it. Look at the obvious method you would use to solve it. What will happen is that you could have a large problem, say size 10,000 (which is beyond hope for many NP-complete problems), you use the obvious method to solve it, and you will be left with an NP-complete problem - which usually has a tiny size, often size 1, unless the original problem is carefully constructed so that the NP-complete subproblem is large.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ can you substantiate that this problem is easy in practice? $\endgroup$
    – wlad
    Commented Feb 2, 2019 at 22:23
  • 1
    $\begingroup$ Note that you can't reason about empirical hardness by looking at the instance size. Tiny instances can be very hard, whereas huge instances are solved in an instant. $\endgroup$
    – Juho
    Commented Feb 3, 2019 at 11:50
  • $\begingroup$ I'd say the bottle filling problem being generally easy to solve is more of a misconception than a fact. People just aren't used to have bottles with sophisticated fractions, and most of the people answering had the implicit assumption (from the OP) that there exists a greedy algorithm for this problem, so it must be easy $\endgroup$
    – Sudix
    Commented Feb 3, 2019 at 16:52
  • $\begingroup$ I didn’t say generally, I said in practical cases. As explained in my answer. $\endgroup$
    – gnasher729
    Commented Feb 3, 2019 at 20:46

Your Answer

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

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