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 :)
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).
> 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.
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.
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.
[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).
> - Require additional space bounded above by an exponential function in the input.
> - May require an unbounded (though obviously finite) amount of time.
How can an algorithm that uses bounded space take unbounded time? Since the computation cannot be in the same memory state twice (otherwise it would loop), if it uses s bits of space it must complete in time O(2^s).
>> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
I think "computationally very hard" means exactly what you say NP-complete problems are ("very hard to solve efficiently"). Typically when one talks about the computational difficulty of an algorithm, they are talking about the computational resources it takes, not the amount a human has to think to come up with the algorithm.
>> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
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).
> 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.
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.
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.
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.
>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).
This is the beauty of randomized analysis in the worst-cases.
The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2).
Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.
This is even more nitpicky, but the worst-case running time can be improved to O(n log n) by choosing the median of the input numbers to be the pivot each time, in O(n) time. This works irrespective of whether the list is sorted or not. This is /not/ useful in practice because of the overhead of choosing the pivot this way, but hey, theory is theory!
"... given a worst-case O(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations this variant is considerably slower on average, but it is of theoretical interest, showing how an optimal selection algorithm can yield an optimal sorting algorithm."
A better way to improve the worst case to O(n log n) time is to use the "Introsort" optimization.[1] Keep track of the recursion depth (with optimized-out tail-recursive calls counted). If the depth exceeds k * log_2(n) [maybe k = 2?], then switch to Heap Sort for the current sublist.
This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation.
Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason.
Introsort is good in practice, but it's not a quicksort.
If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.
I'm familiar with the median-of-medians linear-time selection algorithm (a.k.a. BFPRT). But I don't recall ever seeing a construction of a pivot-finding algorithm using de-randomization. Do you have a reference for this?
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.
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.)
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)
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.
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.
34 comments
[ 3.5 ms ] story [ 62.4 ms ] threadVery 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 :)
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.
There are so many different complexity classes, P and NP are just the start.
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
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
[2] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#...
[3] 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).
> - May require an unbounded (though obviously finite) amount of time.
How can an algorithm that uses bounded space take unbounded time? Since the computation cannot be in the same memory state twice (otherwise it would loop), if it uses s bits of space it must complete in time O(2^s).
In general, SPACE(f(n)) ⊆ DTIME(2^f(n)).
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
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).
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.
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.
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.
This is the beauty of randomized analysis in the worst-cases. The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2).
Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.
"... given a worst-case O(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations this variant is considerably slower on average, but it is of theoretical interest, showing how an optimal selection algorithm can yield an optimal sorting algorithm."
https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation.
Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason.
[1] https://en.wikipedia.org/wiki/Introsort
If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.
Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.
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:
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.
http://en.wikipedia.org/wiki/Hamming_weight
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.