Swipe to navigate through the chapters of this book
Please log in to get access to this content
To get access to this content you need the following product:
You can assume that getting down from Pollux is easy enough. Perhaps there’s a water slide? And that all of this was built before Pollux got so impregnable. Perhaps there was a rockslide?
“An economics professor and a student were strolling through the campus. ‘Look,’ the student cried, ‘there’s a $100 bill on the path!’ ‘No, you are mistaken,’ the wiser head replied. ‘That cannot be. If there were actually a $100 bill, someone would have picked it up.’” (From Compensation, by G. T. Milkovich and J. M. Newman.)
Vinay Deolalikar. P is not equal to NP. August 6, 2010.
Actually, Impagliazzo’s definition of Algorithmica also permits some slightly different scenarios.
Note the “seems to.” We don’t really know whether P = NP, so the definition might actually be equivalent.
Although I don’t make a big fuss about it here, the fact that such problems exist is actually pretty weird.
We need to stick with a polynomial number of nodes, of course.
Both for this section and the following two, you might want to try to show that the examples in the initial paragraphs are, in fact, NP-hard.
To make it easier to follow the arguments in these sections, I’ll generally progress (using reductions) from seemingly simple problems to more expressive ones. In reality, of course, they’re all just as expressive (and hard)—but some problems hide this better than others.
This paragraph is probably easier to understand if you already know a little bit about linear programming. If you didn’t quite catch all of it, don’t worry—it’s not really essential.
Unless we want to take relativity or the curvature of the earth into account ...
Any infinite distances would break it, unless it was completely without edges or consisted of only two nodes.
Note that we always divide the larger of the two (optimum and approximation) by the smaller.
For the minimization case, just reverse the logic, and consider the ratio B/A.
Notice the use of “proof by cases” here. It’s a really useful technique.
I’m guessing he’d think of something better, though.
You might want to verify for yourself that the number of odd-degree nodes in any graph is even.
If you were minimizing, the bounds would, of course, be swapped.
And if you want to get fancy, you could always research some of the many heuristic search methods originating in the field of artificial intelligence, such as genetic programming and tabu search. See the “If You’re Curious ...” section for more.
- Hard Problems and (Limited) Sloppiness
Magnus Lie Hetland
- Sequence number
- Chapter number
- Chapter 11