5
$\begingroup$

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.

  • 0
    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 :)2012-03-01
  • 4
    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.2012-03-01
  • 0
    @HenningMakholm I am already familiar with most of the "textbook reductions", at least known textbooks, still it does not help that much :-(2012-03-01
  • 0
    @Listing Small examples really help with finding efficient algorithms (or counter examples for candidate ones).. They don't seem to help me see the problem is hard.2012-03-01
  • 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_.2012-03-01
  • 0
    @HenningMakholm Good point. If I look at http://en.wikipedia.org/wiki/List_of_NP-complete_problems I think I know on average 2-3 problems from every class. That can be easily improved though, I think..2012-03-01
  • 4
    Have you read Garey and Johnson, Computers and Intractability?2012-03-01
  • 0
    @GerryMyerson No, I haven't. I will try to get a copy.2012-03-02
  • 0
    @GerryMyerson OK, so I am at chapter 3 now, the book seems very promising. It promises in the opening of the chapter that it will prepare the reader to construct hardness proofs on their own. I guess that would entail recognizing hard problems when on sees them as well. Thanks for the great recommendation!2012-03-02
  • 0
    The quickest way to check if something is NP-hard is to see if it can be expressed as a general case of some problem that's already NP-hard (the restriction method). While there are more explicit approaches, it's a lot harder to "see" a reduction if you don't have experience.2012-03-03
  • 0
    @aelguindy Now that ComputerScience.SE is beta, may be you are interested in posting there!2012-03-07
  • 0
    @J.D. Thanks! I tried, it's still in private beta, but I'll keep an eye on it.2012-03-07

2 Answers 2

4

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!