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

• 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.