Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
3  
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
2  
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
3  
Have you read Garey and Johnson, Computers and Intractability? –  Gerry Myerson Mar 1 '12 at 22:37

1 Answer 1

up vote 3 down vote accepted

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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