Rule of thumb to know if a problem could be NP-complete

Problem Detail: 

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.

Asked By : Vitalij Zadneprovskij

Answered By : jmad

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1859