25
$\begingroup$

This question was inspired by a comment on StackOverflow.

Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like an NP-complete one?

I am not looking for something rigorous, but to something that works in most cases.

Of course, every time we have to prove that a problem is NP-complete, or a slight variant of an NP-complete one; but before rushing to the proof it would be great to have certain confidence in the positive result of the proof.

$\endgroup$
  • 8
    $\begingroup$ My rule of thumb is simple: If it doesn't smell like a problem I'm already familiar with, it's probably NP-hard (or worse). $\endgroup$ – JeffE May 15 '12 at 18:49
  • 12
    $\begingroup$ @JeffE of course, you're familiar with quite a few problems by now... newcomers to CS may not be able to use the same rule. $\endgroup$ – Joe May 15 '12 at 20:45
  • 1
    $\begingroup$ @Joe: True. Maybe it would be better to say: If you didn't get the problem from a textbook, it's probably NP-hard. $\endgroup$ – JeffE May 16 '12 at 2:59
  • 2
    $\begingroup$ Another way to put this: it's surprising when a problem is not NP-hard, rather than when a problem is NP-hard. $\endgroup$ – Joe May 16 '12 at 5:02
15
$\begingroup$

This is my personal approach to determine whether a problem (i.e. a language $L$) is NP-complete or not. If both these conditions are verified:

  • I feel that testing if an instance $I$ is in $L$ implies that I need to check all combinations of some sort
  • and that there is no way to split such a combination into two smaller ones

then $L$ may very well be NP-hard.

For example for the subset sum problem, I have to list all subsets of $S$ and check if there is one whose sum is zero. Can I split $S$ into two smaller subsets $S_1$ and $S_2$ on which I will check a similar property? Humm... not really. Maybe if I checked for all combination of $S_1$ and $S_2$ but that would be really long...

Usually the ability to break into smaller pieces is a good indicator for a problem to be in P. This is the divide and conquer approach. For example to find the shortest path between two points, you can use the property that if the shortest path from $A$ to $C$ go through $B$ then it is not longer than the shortest path from $A$ to $B$ plus the shortest from $B$ to $C$.

Quite frankly this approach is very basic: I try to find a (polynomial) algorithm for the given problem. If I can't find one then the problem becomes "hard" in my point of view. Then comes all the NP-completeness reasoning: will I be able to encode an existing NP-complete problem into this one? (And since this is usually much harder, I try once more to find a polynomial algorithm..)

I suspect that this is the usual way of thinking. However it remains quite hard to apply on unknown problems. I personally remember being surprised by one of the first examples of NP-completeness I was told: the clique problem. It seemed so simple to check! So I suppose that experience has a lot to do with it. Also intuition can be useless sometimes. I remember being told several times two almost identical problems but one was in P and the other one with a small variation was NP-complete.

I am yet to find a good example (I need help here), but this is like the post correspondence problem: this is an undecidable problem but some variants are decidable.

$\endgroup$
  • 7
    $\begingroup$ An example I really like is the following one. Take the problem of computing the determinant of a matrix. This is an easy problem in P. Now, simply change the sign in the determinant formula to $+1$ instead of alternating between -1 and +1 and you obtain the permanent, which is a #P-complete problem. $\endgroup$ – Massimo Cafaro May 16 '12 at 8:01
  • 2
    $\begingroup$ An interesting exception to the rule of thumb are optimization problems that can be solved with linear programming. If you havent heard of the trick, it can be hard to see how problems like the the assignment problem or graph matching can be solved in poly time, since tricks like divide and conquer and dynamic programming don't seem to apply. $\endgroup$ – hugomg May 18 '12 at 17:11
  • $\begingroup$ An example is the Longest Common Subsequence problem which is in P for 2 sequences but gets into NP-Hard with more. $\endgroup$ – Christian Vielma Mar 9 '15 at 18:44
14
$\begingroup$

Another perspective on problem-hardness comes from the game and puzzle community, where the rule of thumb is that 'problems are as hard as they possibly can be' (and the exceptions come from hidden structures in the problem - Massimo's example of the determinant in comments is a good instance of this); the trick then comes in understanding how hard a problem can be:

  • Puzzles involving the existence of a static configuration are in NP, and so they tend to be NP-complete; for instance, the polyomino packing problem (can a given set of $n$ polyominos pack a given rectangle of the appropriate area?) is NP-complete.
  • Puzzles involving a sequence of moves within a bounded state space are in PSPACE (since the 'move tree' can generally be explored in standard depth-first manner needing only storage for a polynomial number of configurations), and tend to be PSPACE-complete; a classic example of this is Rush Hour.
  • Games with a polynomially bounded depth are also in PSPACE; this uses the characterization of PSPACE as APTIME, since the usual min-max characterization of strategies perfectly mimics an alternating Turing machine with its characterization as 'there exists a move for player A such that for each reply move from player B, there exists a reply move for player A such that...', etc. They also tend to be PSPACE-complete; Hex and generalized Tic-Tac-Toe games are both examples of this.
  • Games without a bound on tree depth but played in a (polynomially) bounded space are in EXPTIME, since there are exponentially many total positions and the entire graph can be built and explored in time polynomial in the number of positions (and thus exponential overall); these games are generally EXPTIME-complete. Chess, Checkers, and Go all fall into this category.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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