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!

0

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