Don't bother reading the wall of text. Well, the last paragraph is actually decent, but the rest is crap.
This article shows one of the big things that's wrong with mass media in general: overconfident people with a big mouth (or a high WPM) get to reach a hugely disproportionate number of people, when compared with their ability to relate truth. In a world filled with too much information to process, it's more than just unfortunate to have so much inexpert shit to sort through: it's tragic. Can you imagine a world where Glenn Beck starts his show by saying "I have nothing of importance to say today; maybe tomorrow. Here's some music"? Wouldn't it be wonderful?
Oh, sorry I wasn't clear. Yes, my problem is entirely with the word. Specifically, I'd prefer "A reduces to B" to be said as "B solves A". I know it's unimportant, but it's always bugged me (probably more than it should). You make a good point about "solves" possibly implying the solution is completely direct and doesn't require any additional steps. I'm probably much more comfortable with existence results than most CS people, and I use the same mental routines to process them as I do the phrase "B solves A", so the possible indirectness doesn't affect me much. In any case, thanks for humoring me:).
Actually, I meant to assume your machine, as one of its basic operations, can solve the given problem. That is, usually "addition" is a fundamental operation, though a more powerful machine might have "solve the traveling salesman problem" as an "assembly instruction". This is slightly less trivial than it at first might sound. If your machine has dedicated hardware to compute FFTs, and your problem is solved trivially by an FFT, there is a trivial O(1) algorithm for it on that hardware. Interestingly, you can even drop the assumption that your problem is (Turing-)computable, since this magical machine might well be powerful enough to compute things no Turing machine can. Ignoring this assumption, say you have an O(f(n)) algorithm to solve your problem. One way to make an algorithm of strictly (in O-terms) worse runtime is to just run that algorithm O(n) times, ignoring the solution every time but the last. [This is in fact strictly worse: for O(n f(n)) = O(f(n)) means there is a c such that for all n large enough n f(n) is less than c f(n), which makes no sense. Slightly informally, O(f(n)) = O(g(n) f(n)) if and only if g(n) is bounded.]
No, it's alright, I was able to coerce it into a true statement regardless. The restriction that you use a Turing machine, while common, is only implicit. Since that doesn't make sense, you clearly must not have been working with that restriction. So, given an unrestricted algorithm to solve a problem, you can just assume it's running on a machine capable of instantly solving that problem. You can then take the first algorithm to be trivial. The second algorithm with the drastically different run time could be done by inserting a useless but long loop depending on input size. Done!
I'd say similarly problems don't reduce anything; algorithms do. I expand "knapsack solves exact cover" to "if we can solve knapsack, we can turn that solution into a solution for exact cover". The mental picture that goes with that expansion is a long page of code representing knapsack, the apparently more complicated problem, and a shorter page of code representing exact cover, with a function call to the knapsack code. That image and phrase seems to capture your notion of reducibility. Of course it is just semantics, and not terribly important:). I wonder, given the choice, which terminology people first learning the concept would tend to pick.
FLT wasn't terribly deceptive, though. The original conjecture was proven true, and Fermat's intuition borne out as correct. Before its proof, numerous other mathematicians agreed to its truth over the years. A great many mathematicians proved special cases (Euler, Gauss, Lebesgue, and Legendre, to name a few of the most famous from the Wikipedia page; perhaps Fermat himself, though it's hard to say). I've never heard of someone who thought a counterexample would be found. The only deceptive cases I can think of for programmers are very contrived and would be recognizable as "hard" after reading the Wikipedia complexity article instead of a book.
To me, "solves" definitely implies the decidability version. That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B). As ever there are context-dependent restrictions on f--like it must be computable--but those are present regardless. It doesn't seem to me like "reduces" is any more or less precise than "solves".
I suppose I've always assumed programmers have a feel for when their problems are particularly hard. By parallel, in math I would have expected Hilbert's 10th problem to be impossible just from hearing it. (It in fact is impossible.) I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.
My question was why should the above specific programmer study complexity theory. As I mentioned, complexity theory can certainly be useful to actual programmers when they encounter a specific problem that other people have worked on. In that case it seems fine to research the relevant problem on demand, especially considering most programmers are "not working on interesting programs" anyway. To be clear, given that the OP has been fine without complexity theory and is a ways out of academics, why should they study a complexity theory or algs book, or take some theoretical CS course? "Just in case it comes up" seems like a poor answer as above. "To expand their mind" seems decent, though. I'm all for a smarter general population.
Of course I agree that complexity theory has numerous applications, mostly in specific problems and approximations. A P != NP result would represent the culmination of a huge amount of theoretical effort with few practical applications (since we've more or less been assuming it for years anyway). Those who work on the problem while believing P != NP presumably aren't motivated by real-world applications and would likely fit into my category of those who enjoy the study itself. I'm sure complexity theory has relatively fewer of those types than, say, algebraic number theory, though.
its just the polynomial constant or linear coefficient might be like a billion times the age of the universe or something like that.
That would strike me as extremely strange. There are few large constants floating about in proofs. I should be clear that I'm imagining a polynomial time solution for some NP-complete problem, wherein one of the coefficients is minimized by "like a billion times the age of the universe or something like that". It would physically be a bit strange, too, seeing as a change in scale to our universe (say, much, much older) would make the constant unremarkable. Human-scale inconveniences just have no place in such abstract proofs, to my mind. My incredibly uneducated opinion is that P != NP, but that there's a good reason it hasn't been proven--like the question is undecidable in common systems of formal logic, or we're missing a big branch of thought on complexity theory in general.
P(!)=NP reminds me a little of Fermat's Last Theorem. The result most people expect is "no, it's not possible" (...to solve an NP-complete problem in polynomial time, or to find (x, y, z) positive integers where x^n + y^n = z^n for n > 2, respectively). We already knew it would be very difficult, to the point most people think it's impossible. A proof would most likely just confirm suspicions. (Of course FLT was proven, and no, it's not possible. Interestingly it was known for a while that there are at most a finite number of counterexamples for a given n, ignoring multiples, so the final proof just said this finite number is always 0. This had also already been showed for n prime up into the millions via computer, and various other special cases had been proven.)
Perhaps you should read a textbook on computational complexity, or an algorithms text, or just take a course on theoretical computer science?
Why? I'm honestly curious. If the GP has been fine without much complexity theory, and has been out of academics for presumably over a decade, it doesn't seem worth it to bother. From the very little complexity theory I've encountered, it doesn't seem terribly useful to actual programmers unless they have a specific problem that other people have worked on. I don't mean to beat up on complexity theory. I'm a pure math person so I'm fine with theory having a low amount of practical value, where it's studied mostly for the enjoyment of those studying and sometimes out comes an application or two that might spur on grants.
That reminds me of a random annoyance I have with complexity theory. Why use the word "reducible"--as in "exact cover reduces to knapsack". It's more direct to just say knapsack solves exact cover. Most definitions of "reducible" I've seen use "solves" or a variant of the word. I just looked at 3 I found online and two used "solves"; the other used symbols and so avoided the word. Why include an unnecessary reversal? Maybe it's just me, but I always have to translate to make sure I'm not reversing the implication. It's just annoying, and I'm not nearly steeped in complexity theory enough for it to have become natural.
That might be less helpful than you'd think. Suppose they were able to prefetch and reduce adjacent channel switch times to 50ms. I'd want to switch to the next adjacent channel around ~300ms after the first switch, but the prefetching mechanism couldn't have completed its job since this silly TV takes ~1-2 seconds to switch (I timed it more accurately). You'd have to prefetch several adjacent channels to completely eliminate the delay. I don't know how involved it would be hardware-wise to do that. I'd happily accept being forced to channel surf, say, "up", to reduce that complexity.
It takes me around 5 minutes to surf through all my TV channels. Deciding if I want to watch something takes pretty much a single frame, but waiting for channels to switch takes ~1.5-3 seconds. Waves of partly synched commercials keep me from knowing what's on many of those channels. TV Guide channel is basically just as awful, since they make it scroll excruciatingly slowly nowadays. I can go online and get listings, but that's slow and roundabout. I used to have a cable box with the usual channel guide, but the box was so slow it took a second or two to scroll--which was actually much better than my current channel surfing situation.
I'd like to force the TV Guide people to use their own service day-to-day. I bet the scroll speed would triple.
I think the VS2010 reference is in part to the IDE, which has tons of small delays. I just compiled a tiny.NET 4 WPF app (~100 lines and almost no interface), restarted my computer, and launched it. It took several seconds for anything to happen. Presumably various libraries were being loaded as starting a far more complex WPF app was virtually instant afterward. In any case, some delays have nothing to do with the app programmer.
I found windows\system32 containing 64-bit binaries and windows\SysWOW64 containing 32-bit ones worse. I hope they did have a good reason for these strange names, but I haven't seen an explanation.
While I agree that a trial would have been nice, his innocence is not in any doubt. He's been quoted as initially denying and later taking responsibility, eg.
I will explain to you the reasons behind these events, and I will tell you the truth about the moments when this decision was taken, so that you can reflect on it. God knows that the plan of striking the towers had not occurred to us, but the idea came to me when things went just too far with the American-Israeli alliance's oppression and atrocities against our people in Palestine and Lebanon.
(source) A trial may make guilt official, but conviction and guilt are ultimately separate.
I think there could have been serious repercussions from capturing him, like a series of terrorist attacks aimed at releasing him. My guess was that for his intelligence value capture was preferred, but sometimes that's not possible.
1. Starting at the 60 trillionth binary decimal place, pi^2 is, in base 8, 601145053032. Expanding to base 2 this is 110 000 001 001 100 101 000 101 011 000 011 010. You can see more at this post on a blog run by David Bailey and Jonathan Borwein of BBP-type formula fame.
That may have been the GP's point, but it's not really correct. It takes O(n^2) time to compute the nth digit of pi using a modification of the BBP formula. The linked article actually alludes to this fact, though only obliquely, in a reference to exponentiation by squaring. You certainly couldn't compute that manually, as in, with a pencil and paper. All is not lost though; more than the quadrillionth binary digit has been computed (though it took a distributed computing project many months), which is *way* ahead of the highest sequential computations.
Such a result would cause math, physics, and philosophy to come crashing down on everyone's heads. Pi's transcendence (hence, irrationality) is a beautiful consequence of the Lindemann-Weierstrass theorem. The proof of that theorem is, well, hideous, but the statement is incredibly elegant. It turns linear independence into algebraic independence, from which the transcendence of both pi and e may be very quickly deduced. I believe that there are continued fraction proofs of pi's irrationality that are relatively accessible.
Slashdot Mirror
While nothing's perfect, this math major either needs to expand his expertise or to kindly be quiet.
Bah, he really has a master's degree in math, according to his Wikipedia page. That makes me sad.
Don't bother reading the wall of text. Well, the last paragraph is actually decent, but the rest is crap.
This article shows one of the big things that's wrong with mass media in general: overconfident people with a big mouth (or a high WPM) get to reach a hugely disproportionate number of people, when compared with their ability to relate truth. In a world filled with too much information to process, it's more than just unfortunate to have so much inexpert shit to sort through: it's tragic. Can you imagine a world where Glenn Beck starts his show by saying "I have nothing of importance to say today; maybe tomorrow. Here's some music"? Wouldn't it be wonderful?
Oh, sorry I wasn't clear. Yes, my problem is entirely with the word. Specifically, I'd prefer "A reduces to B" to be said as "B solves A". I know it's unimportant, but it's always bugged me (probably more than it should). You make a good point about "solves" possibly implying the solution is completely direct and doesn't require any additional steps. I'm probably much more comfortable with existence results than most CS people, and I use the same mental routines to process them as I do the phrase "B solves A", so the possible indirectness doesn't affect me much. In any case, thanks for humoring me :).
Actually, I meant to assume your machine, as one of its basic operations, can solve the given problem. That is, usually "addition" is a fundamental operation, though a more powerful machine might have "solve the traveling salesman problem" as an "assembly instruction". This is slightly less trivial than it at first might sound. If your machine has dedicated hardware to compute FFTs, and your problem is solved trivially by an FFT, there is a trivial O(1) algorithm for it on that hardware. Interestingly, you can even drop the assumption that your problem is (Turing-)computable, since this magical machine might well be powerful enough to compute things no Turing machine can. Ignoring this assumption, say you have an O(f(n)) algorithm to solve your problem. One way to make an algorithm of strictly (in O-terms) worse runtime is to just run that algorithm O(n) times, ignoring the solution every time but the last. [This is in fact strictly worse: for O(n f(n)) = O(f(n)) means there is a c such that for all n large enough n f(n) is less than c f(n), which makes no sense. Slightly informally, O(f(n)) = O(g(n) f(n)) if and only if g(n) is bounded.]
No, it's alright, I was able to coerce it into a true statement regardless. The restriction that you use a Turing machine, while common, is only implicit. Since that doesn't make sense, you clearly must not have been working with that restriction. So, given an unrestricted algorithm to solve a problem, you can just assume it's running on a machine capable of instantly solving that problem. You can then take the first algorithm to be trivial. The second algorithm with the drastically different run time could be done by inserting a useless but long loop depending on input size. Done!
Problems don't solve anything; algorithms do
I'd say similarly problems don't reduce anything; algorithms do. I expand "knapsack solves exact cover" to "if we can solve knapsack, we can turn that solution into a solution for exact cover". The mental picture that goes with that expansion is a long page of code representing knapsack, the apparently more complicated problem, and a shorter page of code representing exact cover, with a function call to the knapsack code. That image and phrase seems to capture your notion of reducibility. Of course it is just semantics, and not terribly important :). I wonder, given the choice, which terminology people first learning the concept would tend to pick.
FLT wasn't terribly deceptive, though. The original conjecture was proven true, and Fermat's intuition borne out as correct. Before its proof, numerous other mathematicians agreed to its truth over the years. A great many mathematicians proved special cases (Euler, Gauss, Lebesgue, and Legendre, to name a few of the most famous from the Wikipedia page; perhaps Fermat himself, though it's hard to say). I've never heard of someone who thought a counterexample would be found. The only deceptive cases I can think of for programmers are very contrived and would be recognizable as "hard" after reading the Wikipedia complexity article instead of a book.
To me, "solves" definitely implies the decidability version. That is, given two languages A and B, "A solves B" means that there is a map f from B to A where f(x) is in A if and only if x is in B, for all possible x (not just those in B). As ever there are context-dependent restrictions on f--like it must be computable--but those are present regardless. It doesn't seem to me like "reduces" is any more or less precise than "solves".
I suppose I've always assumed programmers have a feel for when their problems are particularly hard. By parallel, in math I would have expected Hilbert's 10th problem to be impossible just from hearing it. (It in fact is impossible.) I answer questions on the math sub-board of a programming forum sometimes and have gotten a few NP(-complete) problems, though they were all easily recognizable as such even with my poor background in complexity theory.
My question was why should the above specific programmer study complexity theory. As I mentioned, complexity theory can certainly be useful to actual programmers when they encounter a specific problem that other people have worked on. In that case it seems fine to research the relevant problem on demand, especially considering most programmers are "not working on interesting programs" anyway. To be clear, given that the OP has been fine without complexity theory and is a ways out of academics, why should they study a complexity theory or algs book, or take some theoretical CS course? "Just in case it comes up" seems like a poor answer as above. "To expand their mind" seems decent, though. I'm all for a smarter general population.
Of course I agree that complexity theory has numerous applications, mostly in specific problems and approximations. A P != NP result would represent the culmination of a huge amount of theoretical effort with few practical applications (since we've more or less been assuming it for years anyway). Those who work on the problem while believing P != NP presumably aren't motivated by real-world applications and would likely fit into my category of those who enjoy the study itself. I'm sure complexity theory has relatively fewer of those types than, say, algebraic number theory, though.
its just the polynomial constant or linear coefficient might be like a billion times the age of the universe or something like that.
That would strike me as extremely strange. There are few large constants floating about in proofs. I should be clear that I'm imagining a polynomial time solution for some NP-complete problem, wherein one of the coefficients is minimized by "like a billion times the age of the universe or something like that". It would physically be a bit strange, too, seeing as a change in scale to our universe (say, much, much older) would make the constant unremarkable. Human-scale inconveniences just have no place in such abstract proofs, to my mind. My incredibly uneducated opinion is that P != NP, but that there's a good reason it hasn't been proven--like the question is undecidable in common systems of formal logic, or we're missing a big branch of thought on complexity theory in general.
P(!)=NP reminds me a little of Fermat's Last Theorem. The result most people expect is "no, it's not possible" (...to solve an NP-complete problem in polynomial time, or to find (x, y, z) positive integers where x^n + y^n = z^n for n > 2, respectively). We already knew it would be very difficult, to the point most people think it's impossible. A proof would most likely just confirm suspicions. (Of course FLT was proven, and no, it's not possible. Interestingly it was known for a while that there are at most a finite number of counterexamples for a given n, ignoring multiples, so the final proof just said this finite number is always 0. This had also already been showed for n prime up into the millions via computer, and various other special cases had been proven.)
Perhaps you should read a textbook on computational complexity, or an algorithms text, or just take a course on theoretical computer science?
Why? I'm honestly curious. If the GP has been fine without much complexity theory, and has been out of academics for presumably over a decade, it doesn't seem worth it to bother. From the very little complexity theory I've encountered, it doesn't seem terribly useful to actual programmers unless they have a specific problem that other people have worked on. I don't mean to beat up on complexity theory. I'm a pure math person so I'm fine with theory having a low amount of practical value, where it's studied mostly for the enjoyment of those studying and sometimes out comes an application or two that might spur on grants.
That reminds me of a random annoyance I have with complexity theory. Why use the word "reducible"--as in "exact cover reduces to knapsack". It's more direct to just say knapsack solves exact cover. Most definitions of "reducible" I've seen use "solves" or a variant of the word. I just looked at 3 I found online and two used "solves"; the other used symbols and so avoided the word. Why include an unnecessary reversal? Maybe it's just me, but I always have to translate to make sure I'm not reversing the implication. It's just annoying, and I'm not nearly steeped in complexity theory enough for it to have become natural.
That might be less helpful than you'd think. Suppose they were able to prefetch and reduce adjacent channel switch times to 50ms. I'd want to switch to the next adjacent channel around ~300ms after the first switch, but the prefetching mechanism couldn't have completed its job since this silly TV takes ~1-2 seconds to switch (I timed it more accurately). You'd have to prefetch several adjacent channels to completely eliminate the delay. I don't know how involved it would be hardware-wise to do that. I'd happily accept being forced to channel surf, say, "up", to reduce that complexity.
It takes me around 5 minutes to surf through all my TV channels. Deciding if I want to watch something takes pretty much a single frame, but waiting for channels to switch takes ~1.5-3 seconds. Waves of partly synched commercials keep me from knowing what's on many of those channels. TV Guide channel is basically just as awful, since they make it scroll excruciatingly slowly nowadays. I can go online and get listings, but that's slow and roundabout. I used to have a cable box with the usual channel guide, but the box was so slow it took a second or two to scroll--which was actually much better than my current channel surfing situation.
I'd like to force the TV Guide people to use their own service day-to-day. I bet the scroll speed would triple.
I think the VS2010 reference is in part to the IDE, which has tons of small delays. I just compiled a tiny .NET 4 WPF app (~100 lines and almost no interface), restarted my computer, and launched it. It took several seconds for anything to happen. Presumably various libraries were being loaded as starting a far more complex WPF app was virtually instant afterward. In any case, some delays have nothing to do with the app programmer.
I found windows\system32 containing 64-bit binaries and windows\SysWOW64 containing 32-bit ones worse. I hope they did have a good reason for these strange names, but I haven't seen an explanation.
While I agree that a trial would have been nice, his innocence is not in any doubt. He's been quoted as initially denying and later taking responsibility, eg.
I will explain to you the reasons behind these events, and I will tell you the truth about the moments when this decision was taken, so that you can reflect on it. God knows that the plan of striking the towers had not occurred to us, but the idea came to me when things went just too far with the American-Israeli alliance's oppression and atrocities against our people in Palestine and Lebanon.
(source) A trial may make guilt official, but conviction and guilt are ultimately separate.
I think there could have been serious repercussions from capturing him, like a series of terrorist attacks aimed at releasing him. My guess was that for his intelligence value capture was preferred, but sometimes that's not possible.
1. See my post in another thread up above for more detail.
(the B's are for Bailey and Borwein)
Urm, what?
1. Starting at the 60 trillionth binary decimal place, pi^2 is, in base 8, 601145053032. Expanding to base 2 this is 110 000 001 001 100 101 000 101 011 000 011 010. You can see more at this post on a blog run by David Bailey and Jonathan Borwein of BBP-type formula fame.
That may have been the GP's point, but it's not really correct. It takes O(n^2) time to compute the nth digit of pi using a modification of the BBP formula. The linked article actually alludes to this fact, though only obliquely, in a reference to exponentiation by squaring. You certainly couldn't compute that manually, as in, with a pencil and paper. All is not lost though; more than the quadrillionth binary digit has been computed (though it took a distributed computing project many months), which is *way* ahead of the highest sequential computations.
Such a result would cause math, physics, and philosophy to come crashing down on everyone's heads. Pi's transcendence (hence, irrationality) is a beautiful consequence of the Lindemann-Weierstrass theorem. The proof of that theorem is, well, hideous, but the statement is incredibly elegant. It turns linear independence into algebraic independence, from which the transcendence of both pi and e may be very quickly deduced. I believe that there are continued fraction proofs of pi's irrationality that are relatively accessible.
Actually, I think he was already using binary ;)