# Proving NP-completeness intuition

When approaching a problem in NP, initially not knowing whether the problem is in P or NP-complete (or some other choice). It seems to me the only way one can go about "solving" this problem is to oscillate between:

1. Attempts to find an efficient algorithm (and finding counter-examples for it).
2. Trying to reduce an NP-complete to it.

until one of the approaches succeed.

In most cases, if the problem is in P, I have a strong intuition about this fact. I tend to spend more time on step (1), even if I don't end up having a solution. If the problem is hard however, I am completely clueless. I have no intuition about this fact whatsoever until I am shown a reduction (or in rare occasions I find it myself). Think of my confidence that a problem is in P as a straight line, that grows the more I think about the problem, while in hard problems, it is a step function (before/after reduction).

What kind of indicators can one look for to see that a problem is hard except the absence of evidence for the converse? How can I develop my intuition to see a problem and think "hmm.. that looks NP-complete"?

I would understand if the question was closed as not constructive, or not a real question, ..etc.

-
A good heuristic is to look at a few instances of the problem and to see how hard it is to solve them by hand, using your intuition. Of course this doesn't always work :) – Listing Mar 1 '12 at 22:09
I think the best (or only) way to be able to say "that looks NP-complete" is to be at least passingly familiar with many different known NP-hard problems. – Henning Makholm Mar 1 '12 at 22:12
@HenningMakholm I am already familiar with most of the "textbook reductions", at least known textbooks, still it does not help that much :-( – aelguindy Mar 1 '12 at 22:16
Being familiar with many reductions is not quite the same as being familiar with many problems. It's valuable to be able to recall that such-and-such problem is NP-hard, even without being able to produce a proof of that fact ex tempore. – Henning Makholm Mar 1 '12 at 22:18
Have you read Garey and Johnson, Computers and Intractability? – Gerry Myerson Mar 1 '12 at 22:37

There are problems that are still not known to be in $P$ or $NP$-hard, so there probably is no definite way to tell that. Moreover, it is possible that some problems are neither in $P$ or $NP$-hard, just in-between. Still I can share my own heuristits when deciding if something is in $P$ or $NP$-hard.

1. Problems in $P$ usually have regular structure and good locality--it is enough to know few local things and some small global state.
2. For problems in $P$ there are usually some bounds that restrict possible number of choices at a given moment disregarding previous decisions, e.g. in BFS algorithm in every moment the size of the queue is at most $n$, independent of which paths you have traversed or which vertexes have visited; similarly the sum of neighbors of all vertexes is bound by $m$, independent of the path by which you have reached them.
3. Problems that are $NP$-hard usually have a subset nature hidden somwhere, i.e. SAT have subsets of variables that are true, TSP has subsets of edges, graph-coloring algorithms have subsets of vertices with given color, Clique has subsets of vertices, etc.
4. Problems that are $NP$-hare are usually non-local--changing color of one vertex may possibly force majority of other colors to be changed, changing one SAT variable may force a lot of others to change their values.
5. Computing some numbers with arbitrary precision can be $NP$-hard; then the intuition is that in that number you could encode a complex problem.
6. There is a class of problems called $FPT$ (Fixed Parameter Tractable), often $NP$-hard problems would have some kernel that is hard, and then if that kernel can be somehow bounded, then the algorithm may be still polynomial; e.g. many graph problems that are $NP$-hard, can solved in $P$ for planar cases or graphs with bounded tree-width.
7. I could go one further, but the hints are less and less usable and I have to finish somewhere, so finally, it is really important what is the input to the algorithm--Knapsack problem is $NP$-complete, but there is a dynamic programming approach that is polynomial if the size of the knapsack is given in base $1$ (i.e. as a string of zeros of appropriate length).

Have fun with those!

-