8 ms·

Helping a stranger, and why you should understand NP-complete

82 points by lifebeyondfife 13y ago

jdmitch 13y ago
Think of NP-complete problems as if they were a brick wall like the red plot in the above graph. Understanding the theory behind the NP-complete complexity class means recognising intractable problems in your code – it’s like having a bomb sniffer dog when walking through a minefield. Very helpful analogy - hadn't thought of it like that. Now I'll know whether the seemingly intractable problems in my code are only temporarily intractable due to my incompetence, or actually intractable for grander reasons :)
ColinWright 13y ago
Here is one case where the original title would be significantly better than the title given: Helping a stranger (and why you should understand NP-complete)
- lifebeyondfife 13y ago
  I ummed and ahhed over it. Really it's two posts, one about helping someone out and another about NP-complete problems in the wild. Thought I'd go with the Hacker News angle for Hacker News (hopefully to encourage / keep up the helping).
  - p4bl0 13y ago
    Well, for me the Hacker News angle would have been the part about NP-complete problems ;-).
- idProQuo 13y ago
  Never fear! The mods will change it back as soon as they catch on.
  - deleted 13y ago
    [deleted]
thaumasiotes 13y ago
> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard It's totally correct, but it always bothers me a little to see people talk about NP in those terms; much, much more difficult problems are known. Recreational wikipedia reading taught me a while ago the the regexp equivalence problem ("do these two given regular expressions define the same language?") is EXPSPACE-complete, where EXPSPACE contains all the problems that: - Require additional space bounded above by an exponential function in the input. - May require an unbounded (though obviously finite) amount of time. That second point is a doozy, and the problem so accessible that I'm fairly sure many people have independently come up with it and wished for a solution. That's not going to happen, though; a solution would be good for much more than just deciding whether two regexps are equivalent. Any NP-complete problem is utterly trivial by comparison.
- lifebeyondfife 13y ago
  Yep, totally agree - it gets so much worse. I don't recall going much further than NP hard in my undergraduate courses but another guy I did my PhD with was a researcher into QSAT which is PSPACE-complete (fails the "verify a token in polynomial time" condition of NP-complete). There are so many different complexity classes, P and NP are just the start.
- gphilip 13y ago
  A different but related point: NP-hard problems (and other kind of hard problems, like EXPSPACE-hard problems) are (in general) hard only _in the worst case_. This means that a problem might be NP-hard (or worse), but we may have algorithms which solve every instance of the problem which could possibly arise _in practice_ "fast". This is because for these problems, the really hard instances are so very rare and/or esoteric that they don't turn up in practice. A case in point is the granddaddy of them all, the Boolean Satisfiability Problem [1], or SAT for short, which was the first problem shown to be NP-hard. We now have algorithms which can solve, in reasonable amounts of time, SAT instances which contain up to millions of clauses [2]: "... efficient and scalable algorithms for SAT were developed over the last decade and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints" Another way in which NP-and-other hardness does not necessarily spell doom in practice is illustrated by the problem of type-checking programs written in the functional language ML (or in another language which has a Hindley-Milner type system). This problem is hard (and complete) for the class EXPTIME [3] (which means: much worse than NP-hard), but this doesn't pose problems in practice: modern ML compilers can easily type-check large programs which are thrown at them. One "explanation" for this contrast is given by the existence of an algorithm for type-checking ML programs [4] which runs in time O(2^{k} n) where a) n is the size of the program, and b) k is the maximum _nesting depth_ of type declarations in the program Since programs which are written by humans (or otherwise found in the wild) do not usually have type declarations more than about 10-deep or so, this algorithm solves the type-checking problem (which is extremely hard, in theory!) in essentially _linear_ time in the input size. So the bottom line is that a problem being NP-(or worse)-hard doesn't automatically mean that we can't actually solve it in practice. [1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem [2] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#... [3] http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00092.html http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00... [4] Orna Lichtenstein and Amir Pnueli. 1985. Checking that finite state concurrent programs satisfy their linear specification. In Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '85).
kfk 13y ago
You have to be knowledgeable about a domain that can’t easily be simplified by series of web searches, and more importantly, there has to be a suggestion that someone might be seeking that clarification. You won't believe how difficult is to offer help if you are not a professional programmer of some sort (in HN and outside HN). Even for open source projects. Even if you try to provide insights on your "professional" job that, in theory, is full of "startup potential" (finance, like we are still using MS Access and messy spreadsheets).
gms7777 13y ago
> They can tell you that the most efficient algorithm for ordering (randomised) data is Quicksort, which has a Big-O notation of O(nlogn) I know this is nitpicky, but quicksort is, worst-case, O(n^2), meaning a large number of comparison based sorting algorithms are faster than it. Its in the average case that Quicksort wins.
- lifebeyondfife 13y ago
  That's why I said "(randomised)". The worst case occurs when the list to be sorted is already ordered and you select the head of the list as the pivot point. Even though other algorithms such as Mergesort also have O(nlogn), Quicksort is normally the preferred implementation because it's relatively easy to do in-place and generally is the most efficient[1] of all the sorting algorithms. [1]Not my field of expertise though, happy to be told I'm wrong.
  - gms7777 13y ago
    You're definitely not wrong, its generally the fastest. Efficient is a bit of a loaded worded in these contexts, and I feel as though when discussiing algorithms, unless otherwise specified, the assumption is you're discussing worst-case efficiency (because while worst case isn't always the most useful metric, is usually the most easily defined and derived one). And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness). As I said though, that is an entirely nitpicky point.
    - lifebeyondfife 13y ago
      I see what you mean. Thanks for taking the time out to nitpick.
    - eru 13y ago
      Randomized QuickSort has an expected worst case runtime of O(n log n). To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime. This is different from an average (over all inputs) run time.
saosebastiao 13y ago
Great post, I really enjoyed it. I wish there were more people with your skill set in my realm of expertise...it is amazing how many problems could be solved if they can be identified, classified, and attacked methodically like you just showed (instead of loosey-goosey hand-cobbled code). I can think of a few huge problems (big $$$) in my org that could be optimized really well if we had more people that could understand and apply constraint programming.
- eru 13y ago
  You might want to check out Zimpl. It's a language to make it real simple to formulate mixed linear programming problem. (Mixed here means integer and continuous.)
fjwolski 13y ago
There're few other things you can do to possibly speed up the second code snippet, by reducing dimensionality: 1) recognize q1 * q2 = 2^p1 * 2^p2 = 2^(p1 + p2), so instead of iterating over q1 then q2, iterate over p = p1 + p2 2) memorize some of the combinations; e.g. if you iterate over p, r1 & r2, then you know that all you're trying to find is two integers f1 & f2 that are equal to output * r1 * r2 * 2^p / input; so before you start solving the problem, calculate table T: for (int f1 = 1; f1 <= 256; ++f1) for (int f2 = 1; f2 <= 256; ++f2) T[f1 * f2] = f1 now you can check whether integer pair (f1,f2) exists, you can just check whether T[output * r1 * f2 * 2^p / input] is non-zero. Also, output * r1 * r2 * 2^p has to be divisible by input, so after you iterate over p & r1, you can iterate only over r2's being multiples of input / gcd(input, output * r1 * 2^p) There could be possibly some more tricks found.
- bazzargh 13y ago
  Another way to reduce the number of loops: for (int q2 = 1; q2 <= 256; q2 <<= 1) if (output * r1 * r2 * q1 * q2 == input * f1 * f2) This doesn't need a loop. Set q2 directly and test if it is a power of 2. n2 = input * f1 * f2; d2 = output * r1 * r2 * q1; q2 = n2/d2; if (__builtin_popcount(q2) == 1 && q2 * d2 == n2) { ... taking advantage of the fact that calculating the Hamming weight of q2 doesn't need a loop. http://en.wikipedia.org/wiki/Hamming_weight http://en.wikipedia.org/wiki/Hamming_weight
deleted 13y ago
[deleted]
deleted 13y ago
[deleted]
danbruc 13y ago
The first point of your definition of NP-completeness is backwards - every problem in NP must be reducible to the problem, not the other way round. The paragraph following the definition has it backwards, too.
- deleted 13y ago
  [deleted]
picomancer 13y ago
This is actually a number theory problem. You want to have input * A = output * B (1) where A = f1 * f2 (2) B = r1 * r2 * q1 * q2 (3) where q1, q2 are powers of two. Any good elementary number theory book will tell you that the smallest solution to (1) is to let M = lcm(input, output) and set A = M / input, B = M / output. Given the further constraint that A <= 2^16, you can compute offline a 2^16 element lookup table which gives values of f1, f2 in the desired ranges for each possible value of A. You can re-use the same table to go from your B value to r1, r2 if you first pull out as many powers of two as you can and put them in q1, q2.

Think of NP-complete problems as if they were a brick wall like the red plot in the above graph. Understanding the theory behind the NP-complete complexity class means recognising intractable problems in your code – it’s like having a bomb sniffer dog when walking through a minefield. Very helpful analogy - hadn't thought of it like that. Now I'll know whether the seemingly intractable problems in my code are only temporarily intractable due to my incompetence, or actually intractable for grander reasons :)

ColinWright 13y ago

Here is one case where the original title would be significantly better than the title given: Helping a stranger (and why you should understand NP-complete)

lifebeyondfife 13y ago
I ummed and ahhed over it. Really it's two posts, one about helping someone out and another about NP-complete problems in the wild. Thought I'd go with the Hacker News angle for Hacker News (hopefully to encourage / keep up the helping).
- p4bl0 13y ago
  Well, for me the Hacker News angle would have been the part about NP-complete problems ;-).
idProQuo 13y ago
Never fear! The mods will change it back as soon as they catch on.
- deleted 13y ago
  [deleted]

thaumasiotes 13y ago

> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard It's totally correct, but it always bothers me a little to see people talk about NP in those terms; much, much more difficult problems are known. Recreational wikipedia reading taught me a while ago the the regexp equivalence problem ("do these two given regular expressions define the same language?") is EXPSPACE-complete, where EXPSPACE contains all the problems that: - Require additional space bounded above by an exponential function in the input. - May require an unbounded (though obviously finite) amount of time. That second point is a doozy, and the problem so accessible that I'm fairly sure many people have independently come up with it and wished for a solution. That's not going to happen, though; a solution would be good for much more than just deciding whether two regexps are equivalent. Any NP-complete problem is utterly trivial by comparison.

lifebeyondfife 13y ago
Yep, totally agree - it gets so much worse. I don't recall going much further than NP hard in my undergraduate courses but another guy I did my PhD with was a researcher into QSAT which is PSPACE-complete (fails the "verify a token in polynomial time" condition of NP-complete). There are so many different complexity classes, P and NP are just the start.
gphilip 13y ago
A different but related point: NP-hard problems (and other kind of hard problems, like EXPSPACE-hard problems) are (in general) hard only _in the worst case_. This means that a problem might be NP-hard (or worse), but we may have algorithms which solve every instance of the problem which could possibly arise _in practice_ "fast". This is because for these problems, the really hard instances are so very rare and/or esoteric that they don't turn up in practice. A case in point is the granddaddy of them all, the Boolean Satisfiability Problem [1], or SAT for short, which was the first problem shown to be NP-hard. We now have algorithms which can solve, in reasonable amounts of time, SAT instances which contain up to millions of clauses [2]: "... efficient and scalable algorithms for SAT were developed over the last decade and have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints" Another way in which NP-and-other hardness does not necessarily spell doom in practice is illustrated by the problem of type-checking programs written in the functional language ML (or in another language which has a Hindley-Milner type system). This problem is hard (and complete) for the class EXPTIME [3] (which means: much worse than NP-hard), but this doesn't pose problems in practice: modern ML compilers can easily type-check large programs which are thrown at them. One "explanation" for this contrast is given by the existence of an algorithm for type-checking ML programs [4] which runs in time O(2^{k} n) where a) n is the size of the program, and b) k is the maximum _nesting depth_ of type declarations in the program Since programs which are written by humans (or otherwise found in the wild) do not usually have type declarations more than about 10-deep or so, this algorithm solves the type-checking problem (which is extremely hard, in theory!) in essentially _linear_ time in the input size. So the bottom line is that a problem being NP-(or worse)-hard doesn't automatically mean that we can't actually solve it in practice. [1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem [2] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Algorithms_for_solving_SAT http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#... [3] http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00092.html http://www.seas.upenn.edu/~sweirich/types/archive/1989/msg00... [4] Orna Lichtenstein and Amir Pnueli. 1985. Checking that finite state concurrent programs satisfy their linear specification. In Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '85).

kfk 13y ago

You have to be knowledgeable about a domain that can’t easily be simplified by series of web searches, and more importantly, there has to be a suggestion that someone might be seeking that clarification. You won't believe how difficult is to offer help if you are not a professional programmer of some sort (in HN and outside HN). Even for open source projects. Even if you try to provide insights on your "professional" job that, in theory, is full of "startup potential" (finance, like we are still using MS Access and messy spreadsheets).

gms7777 13y ago

> They can tell you that the most efficient algorithm for ordering (randomised) data is Quicksort, which has a Big-O notation of O(nlogn) I know this is nitpicky, but quicksort is, worst-case, O(n^2), meaning a large number of comparison based sorting algorithms are faster than it. Its in the average case that Quicksort wins.

lifebeyondfife 13y ago
That's why I said "(randomised)". The worst case occurs when the list to be sorted is already ordered and you select the head of the list as the pivot point. Even though other algorithms such as Mergesort also have O(nlogn), Quicksort is normally the preferred implementation because it's relatively easy to do in-place and generally is the most efficient[1] of all the sorting algorithms. [1]Not my field of expertise though, happy to be told I'm wrong.
- gms7777 13y ago
  You're definitely not wrong, its generally the fastest. Efficient is a bit of a loaded worded in these contexts, and I feel as though when discussiing algorithms, unless otherwise specified, the assumption is you're discussing worst-case efficiency (because while worst case isn't always the most useful metric, is usually the most easily defined and derived one). And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness). As I said though, that is an entirely nitpicky point.
  - lifebeyondfife 13y ago
    I see what you mean. Thanks for taking the time out to nitpick.
  - eru 13y ago
    Randomized QuickSort has an expected worst case runtime of O(n log n). To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime. This is different from an average (over all inputs) run time.

saosebastiao 13y ago

Great post, I really enjoyed it. I wish there were more people with your skill set in my realm of expertise...it is amazing how many problems could be solved if they can be identified, classified, and attacked methodically like you just showed (instead of loosey-goosey hand-cobbled code). I can think of a few huge problems (big $$$) in my org that could be optimized really well if we had more people that could understand and apply constraint programming.

eru 13y ago
You might want to check out Zimpl. It's a language to make it real simple to formulate mixed linear programming problem. (Mixed here means integer and continuous.)

fjwolski 13y ago

There're few other things you can do to possibly speed up the second code snippet, by reducing dimensionality: 1) recognize q1 * q2 = 2^p1 * 2^p2 = 2^(p1 + p2), so instead of iterating over q1 then q2, iterate over p = p1 + p2 2) memorize some of the combinations; e.g. if you iterate over p, r1 & r2, then you know that all you're trying to find is two integers f1 & f2 that are equal to output * r1 * r2 * 2^p / input; so before you start solving the problem, calculate table T: for (int f1 = 1; f1 <= 256; ++f1) for (int f2 = 1; f2 <= 256; ++f2) T[f1 * f2] = f1 now you can check whether integer pair (f1,f2) exists, you can just check whether T[output * r1 * f2 * 2^p / input] is non-zero. Also, output * r1 * r2 * 2^p has to be divisible by input, so after you iterate over p & r1, you can iterate only over r2's being multiples of input / gcd(input, output * r1 * 2^p) There could be possibly some more tricks found.

bazzargh 13y ago
Another way to reduce the number of loops: for (int q2 = 1; q2 <= 256; q2 <<= 1) if (output * r1 * r2 * q1 * q2 == input * f1 * f2) This doesn't need a loop. Set q2 directly and test if it is a power of 2. n2 = input * f1 * f2; d2 = output * r1 * r2 * q1; q2 = n2/d2; if (__builtin_popcount(q2) == 1 && q2 * d2 == n2) { ... taking advantage of the fact that calculating the Hamming weight of q2 doesn't need a loop. http://en.wikipedia.org/wiki/Hamming_weight http://en.wikipedia.org/wiki/Hamming_weight

deleted 13y ago

[deleted]

deleted 13y ago

[deleted]

danbruc 13y ago

The first point of your definition of NP-completeness is backwards - every problem in NP must be reducible to the problem, not the other way round. The paragraph following the definition has it backwards, too.

deleted 13y ago
[deleted]

picomancer 13y ago

This is actually a number theory problem. You want to have input * A = output * B (1) where A = f1 * f2 (2) B = r1 * r2 * q1 * q2 (3) where q1, q2 are powers of two. Any good elementary number theory book will tell you that the smallest solution to (1) is to let M = lcm(input, output) and set A = M / input, B = M / output. Given the further constraint that A <= 2^16, you can compute offline a 2^16 element lookup table which gives values of f1, f2 in the desired ranges for each possible value of A. You can re-use the same table to go from your B value to r1, r2 if you first pull out as many powers of two as you can and put them in q1, q2.