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:


*

*Attempts to find an efficient algorithm (and finding counter-examples for it).

*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: 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.


*

*Problems in $P$ usually have regular structure and good locality--it is enough to know few local things and some small global state.

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

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

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

*Computing some numbers with arbitrary precision can be $NP$-hard; then the intuition is that in that number you could encode a complex problem.

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

*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!
A: (This is only my personal opinion)
To develop my intuition to see a problem and think "hmm.. that looks NP-complete", you will surely need to see different types of (basic) reductions. "Computers and Intractability" by Garey and Johnson and "The NP-completeness column: An ongoing guide" are excellent resources. Also, it is impossible to overemphasize this: Do exercise reductions 
(Exercises in Garey&Johnson are nice; if you are too familiar with it, try some new exercise you haven't tried from some other source; questions people have a feeling that it must be NP-complete but fail to pinpoint exactly how: you will get a lot of such problems in theoretical computer science.se and a  few in maths.se)
I shall discuss about something that complements this -- developing an intuition to think "hmm.. that cannot be NP-complete". When you try out different reductions to your problem, you will get an increasing feeling that your problem it too limited in the sense it has not much expressive power to express those problems. Personally, I find coming up with algorithms that you feel to be polynomial time solvable harder than coming up with a reduction when you have a feeling that it must be NP-complete.
Oscillating between attempts to solve the problem efficently and showing that the problem is NP-hard is always there. But they complement each other most of the time rather than go in parallel.
