Well, you don't need to feel bad about not understanding the PCP theorem. It's a difficult concept to grasp. For example, you could be an extremely intelligent and motivated high school student who can't "get it" even if you try, because you just haven't studied all the pre-requisite material you need. Though perhaps you can't go to the PCP theorem from where you are now, you might be able to understand it once you have all the background knowledge.
The original poster described the PCP theorem well, but it might not make a lot of sense to people who haven't studied algorithms or complexity theory. This might help:
A lot of problems people want to solve in practice are "optimization" problems. That is, given a problem, we want to find the optimum (minimum or maximum, as the case may be) solution. For example, if you have to travel to several cities, you might want to know the cost of the cheapest tour that visits all of them. Or you might want to know what the most efficient way of scheduling jobs on a machine is.
These (and several other) problems, are what we call NP-Hard. That has a technical meaning, but in short, it takes a *really* long time (far more than is practical) to compute the best solutions for these problems. And so if you wanted a solution, instead of spending forever to find the best tour, you might settle for a tour that cost only 1% more, if you could find it quickly. Algorithms which do this are called approximation algorithms; they don't always find the best solution, but they approximate it - the solution they find is nearly as good... perhaps just a little more expensive or less inefficient.
Approximation algorithms are useful because people are often satisfied with solutions that are "good enough", even if not perfect. So for a hard problem, it's worth spending time trying to find a good approximate solution.
Enter the PCP theorem! You can use it to show that some problems can't even be approximately solved in a reasonable amount of time, and that's what the original poster was talking about.
Besides this, the theorem is important and loved because not only is it useful, it's non-obvious and beautiful
If I'm reading you correctly, the argument that you're making is that America began a war in Iraq because it would be an effective way to 'enhance our own safety and security, both physically and economically' and modernize the Middle East. The other options were either too difficult, or would cause unacceptable instability.
Have you ever considered that America might not have the right to make such a decision? If one country decides to invade a neighbor to enhance its own security, wouldn't you condemn it? What makes America different? Would Soviet Russia have been right to attack America? There are only two responses I can think of: a) My country, right or wrong. b) America can defend itself, so anyone who wants to invade is welcome to try. The first is completely immoral, and the second would rapidly lead to anarchy.
You pointed out that you were modernizing Iraq; why should your vision of a modern country be imposed on another? If Russia had believed that communism was intrisically better than democracy, wouldn't they have been right to attack America?
Of course, if Iraq had attacked America, I wouldn't complain; I agree that the invasion of Afghanistan was justified. One could even argue that if Iraq had been planning to attack America, the invasion would have been justifiable. But to attack a country that has not harmed you in order to promote your own interests is in complete violation of international law, and no other country would be allowed to get away with it.
For the record, I despised (and still despise) Saddam Hussein, and agree that regime change was a desirable goal. The end did not, however, justify the means used.
To achieve the goal of building dependable computer systems, the scientists suggest building a verifying compiler, a tool that proves automatically that a program is correct before allowing it to run -- something first written about in the 1950s.
It isn't even possible to always decide whether a program will terminate, let alone 'work correctly'. Have the 'scientists' never heard of The Halting Problem? Perhaps the scientists only meant a compiler that verifies programs from a very limited domain, but then the journalist should be shot for ridiculous exaggeration.
If you noticed, I said that *everything else being equal*, there would be a 90% drop in current. Current is proportional to the rate of electron flow. If there are half as many electrons, but with greater mobility, you haven't decreased the current by a factor of two.
And besides, what I was really trying to point out was that the OP was completely wrong with his 81%-less-power. 90% less currrent implies that the new current is only a tenth of the old current, not 90% of it. One would think that on Slashdot, posters would be able to handle basic arithmetic. (Or if not, at least the mods would.)
If there is 90% less current, there is a 99% saving in Power, not 19%. The new current is 0.1I, so the new power is (0.1 I)^2 R = 0.01 I^2R
I'm not sure that 90% less electrons immediately leads to 90% less current, though. Everything else being equal, this is true, but perhaps other factors have changed as well.
Re:Cool! Just like form AutoComplete
on
Google Suggest
·
· Score: 1
In that case, it's completely understandable!:-)
Right after I hit the submit button and went back to the thread, I saw the clarifications and realised that you knew what he meant. I guess I deserve a (-1, Redundant). Oh, well...:-)
Re:Cool! Just like form AutoComplete
on
Google Suggest
·
· Score: 1
No, you still don't get what he meant. He understands that the algorithm has a quadratic running time; he wants to know what the measure of input size is. Is it quadratic in the dictionary size or quadratic in the size of the typed input?
If I told you a new graph algorithm I developed had a linear running time, it's entirely reasonable to ask if I meant linear in the number of vertices V, the number of edges E, or the V + E which is usually meant. These are three entirely different running times!
(For the record, I'm a Ph.D. student at UIUC studying algorithms.)
It works just fine with Opera 7.54
on
Google Suggest
·
· Score: 1
Did you even try? It works perfectly for me. If you have personal information which you want Opera to use for Autocomplete, both show up.
Unfortunately, there seems to be no perfect way to disambiguate with the keyboard, but that's a minor quibble. If it bothers you, temporarily disable Opera's Autocomplete. I find that I can usually manage with the keyboard, but the keyboard+mouse combination is fast on the rare occasions both the terms have a long prefix in common.
Mostly accurate post, but you had an error in the definition of NP-Complete problems. You said "an NP-complete problem is an NP problem that can map to any other NP problem." Actually, an NP-Complete problem is an NP problem to which all NP problems can be mapped. That is, a problem A is NP-Complete if all problems in NP can be mapped to it, not if A can be mapped to all problems in NP.
Even if P=NP, there will exist NP-Complete problems which cannot be mapped to all problems in NP.
This is a good analogy? The fact that polls show Michael Badnarik receiving 4% of the votes does not mean that he has a 4% chance of winning the election. He will win if a large number of main party supporters change their votes, and the probability of that happening is a lot less than 4%, or even 0.04%, for that matter.
And your vote clearly makes a difference. When polls show several states going down to the wire, when Gore won New Mexico by 366 votes in the last election, it's ridiculous to believe that your vote is irrelevant. Even if the candidate you support cannot win, your vote is important as an indicator of public opinion.
And now, just to be contrarian, I'll admit that I agree with a good deal of the libertarian philosophy myself. Of course, since I'm not an American citizen, my preference is irrelevant. Still, my beliefs don't alter the fact that this analogy is absurd.
From the CNN article: Black holes [are] typically much more massive than Earth.
Re:"Surely You're Joking, Mr. Feynman!"
on
Good Bad Attitude
·
· Score: 2, Informative
Not quite... The wife of Dean Eisenhart (Dean of the Graduate College at Princeton when Feynman was a grad student there) said this when Feynman committed the social gaffe of saying that he wanted both cream and lemon in his tea.
Have you tried googling for physical science or penetration mechanics lately? (Quotes not even required, and there's no reason why you shouldn't have expected to need them).
A lot easier to make baseless comments than verify your allegations, isn't it?
And who modded that insightful?
Your mathematics is impeccable; 3 tests of 5 users each should, with those assumptions, find less of the original bugs than 1 test of 15 users. That isn't very rational, but when was math ever rational?:-)
What you didn't consider, though, is that the designers make changes after every test with 5 users. So after the first test finds 80% of the problems, they are corrected, but perhaps some new ones are introduced. The new users find 80% of the original problems that were undiscovered, AND 80% of the new problems. And then there's another iteration.
The advantage, therefore, is that you discover almost all the original problems and also get to try out possible fixes and uncover problems with the fixes
Well, I have anecdotal evidence. A company in Delhi (the capital of India) contacted my sister about a year ago and asked her to click on ads for them. The pay wasn't great (certainly nothing like a college graduate makes), but as much as many Indians make at a full-time job.
After my sister told me about this, I checked up on the company out of curiosity. Terrible website, you could tell at a glance that this was borderline illegal/unethical/sleazy just from their website. But I've found several people who work for similar companies. Often they're bored housewives who don't mind working a couple of hours per day to earn some spending money.
One idea though - why not add one of those little "Are you a terrorist?" tick-boxes when you buy tickets?
Quoting from the second page of the US Department of State's current Form DS-156, Nonimmigrant Visa Application: Do you seek to enter the United States to engage in export control violations, subversive or terrorist activities, or any other unlawful purpose? Are you a member or representative of a terrorist organization as currently designated by the U.S. Secretary of State? (Y/N)
Slashdot Mirror
Well, you don't need to feel bad about not understanding the PCP theorem. It's a difficult concept to grasp. For example, you could be an extremely intelligent and motivated high school student who can't "get it" even if you try, because you just haven't studied all the pre-requisite material you need. Though perhaps you can't go to the PCP theorem from where you are now, you might be able to understand it once you have all the background knowledge.
The original poster described the PCP theorem well, but it might not make a lot of sense to people who haven't studied algorithms or complexity theory. This might help:
A lot of problems people want to solve in practice are "optimization" problems. That is, given a problem, we want to find the optimum (minimum or maximum, as the case may be) solution. For example, if you have to travel to several cities, you might want to know the cost of the cheapest tour that visits all of them. Or you might want to know what the most efficient way of scheduling jobs on a machine is. These (and several other) problems, are what we call NP-Hard. That has a technical meaning, but in short, it takes a *really* long time (far more than is practical) to compute the best solutions for these problems. And so if you wanted a solution, instead of spending forever to find the best tour, you might settle for a tour that cost only 1% more, if you could find it quickly. Algorithms which do this are called approximation algorithms; they don't always find the best solution, but they approximate it - the solution they find is nearly as good... perhaps just a little more expensive or less inefficient.
Approximation algorithms are useful because people are often satisfied with solutions that are "good enough", even if not perfect. So for a hard problem, it's worth spending time trying to find a good approximate solution.
Enter the PCP theorem! You can use it to show that some problems can't even be approximately solved in a reasonable amount of time, and that's what the original poster was talking about.
Besides this, the theorem is important and loved because not only is it useful, it's non-obvious and beautiful
Dave,
If I'm reading you correctly, the argument that you're making is that America began a war in Iraq because it would be an effective way to 'enhance our own safety and security, both physically and economically' and modernize the Middle East. The other options were either too difficult, or would cause unacceptable instability.
Have you ever considered that America might not have the right to make such a decision? If one country decides to invade a neighbor to enhance its own security, wouldn't you condemn it? What makes America different? Would Soviet Russia have been right to attack America? There are only two responses I can think of:
a) My country, right or wrong.
b) America can defend itself, so anyone who wants to invade is welcome to try.
The first is completely immoral, and the second would rapidly lead to anarchy.
You pointed out that you were modernizing Iraq; why should your vision of a modern country be imposed on another? If Russia had believed that communism was intrisically better than democracy, wouldn't they have been right to attack America?
Of course, if Iraq had attacked America, I wouldn't complain; I agree that the invasion of Afghanistan was justified. One could even argue that if Iraq had been planning to attack America, the invasion would have been justifiable. But to attack a country that has not harmed you in order to promote your own interests is in complete violation of international law, and no other country would be allowed to get away with it.
For the record, I despised (and still despise) Saddam Hussein, and agree that regime change was a desirable goal. The end did not, however, justify the means used.
To achieve the goal of building dependable computer systems, the scientists suggest building a verifying compiler, a tool that proves automatically that a program is correct before allowing it to run -- something first written about in the 1950s.
It isn't even possible to always decide whether a program will terminate, let alone 'work correctly'. Have the 'scientists' never heard of The Halting Problem?
Perhaps the scientists only meant a compiler that verifies programs from a very limited domain, but then the journalist should be shot for ridiculous exaggeration.
unless the electrons go around twice... as fast!
If you noticed, I said that *everything else being equal*, there would be a 90% drop in current. Current is proportional to the rate of electron flow. If there are half as many electrons, but with greater mobility, you haven't decreased the current by a factor of two.
And besides, what I was really trying to point out was that the OP was completely wrong with his 81%-less-power. 90% less currrent implies that the new current is only a tenth of the old current, not 90% of it. One would think that on Slashdot, posters would be able to handle basic arithmetic. (Or if not, at least the mods would.)
If there is 90% less current, there is a 99% saving in Power, not 19%. The new current is 0.1I, so the new power is (0.1 I)^2 R = 0.01 I^2R
I'm not sure that 90% less electrons immediately leads to 90% less current, though. Everything else being equal, this is true, but perhaps other factors have changed as well.
In that case, it's completely understandable! :-) :-)
Right after I hit the submit button and went back to the thread, I saw the clarifications and realised that you knew what he meant. I guess I deserve a (-1, Redundant). Oh, well...
No, you still don't get what he meant. He understands that the algorithm has a quadratic running time; he wants to know what the measure of input size is. Is it quadratic in the dictionary size or quadratic in the size of the typed input?
If I told you a new graph algorithm I developed had a linear running time, it's entirely reasonable to ask if I meant linear in the number of vertices V, the number of edges E, or the V + E which is usually meant. These are three entirely different running times!
(For the record, I'm a Ph.D. student at UIUC studying algorithms.)
Did you even try? It works perfectly for me. If you have personal information which you want Opera to use for Autocomplete, both show up.
Unfortunately, there seems to be no perfect way to disambiguate with the keyboard, but that's a minor quibble. If it bothers you, temporarily disable Opera's Autocomplete. I find that I can usually manage with the keyboard, but the keyboard+mouse combination is fast on the rare occasions both the terms have a long prefix in common.
Mostly accurate post, but you had an error in the definition of NP-Complete problems. You said "an NP-complete problem is an NP problem that can map to any other NP problem." Actually, an NP-Complete problem is an NP problem to which all NP problems can be mapped. That is, a problem A is NP-Complete if all problems in NP can be mapped to it, not if A can be mapped to all problems in NP.
Even if P=NP, there will exist NP-Complete problems which cannot be mapped to all problems in NP.
This is a good analogy? The fact that polls show Michael Badnarik receiving 4% of the votes does not mean that he has a 4% chance of winning the election. He will win if a large number of main party supporters change their votes, and the probability of that happening is a lot less than 4%, or even 0.04%, for that matter.
And your vote clearly makes a difference. When polls show several states going down to the wire, when Gore won New Mexico by 366 votes in the last election, it's ridiculous to believe that your vote is irrelevant. Even if the candidate you support cannot win, your vote is important as an indicator of public opinion.
And now, just to be contrarian, I'll admit that I agree with a good deal of the libertarian philosophy myself. Of course, since I'm not an American citizen, my preference is irrelevant. Still, my beliefs don't alter the fact that this analogy is absurd.
From the CNN article: Black holes [are] typically much more massive than Earth.
Not quite... The wife of Dean Eisenhart (Dean of the Graduate College at Princeton when Feynman was a grad student there) said this when Feynman committed the social gaffe of saying that he wanted both cream and lemon in his tea.
:-)
I have no idea why I know this...
Have you tried googling for physical science or penetration mechanics lately? (Quotes not even required, and there's no reason why you shouldn't have expected to need them).
A lot easier to make baseless comments than verify your allegations, isn't it?
And who modded that insightful?
Your mathematics is impeccable; 3 tests of 5 users each should, with those assumptions, find less of the original bugs than 1 test of 15 users. That isn't very rational, but when was math ever rational? :-)
What you didn't consider, though, is that the designers make changes after every test with 5 users. So after the first test finds 80% of the problems, they are corrected, but perhaps some new ones are introduced. The new users find 80% of the original problems that were undiscovered, AND 80% of the new problems. And then there's another iteration.
The advantage, therefore, is that you discover almost all the original problems and also get to try out possible fixes and uncover problems with the fixes
Well, I have anecdotal evidence. A company in Delhi (the capital of India) contacted my sister about a year ago and asked her to click on ads for them. The pay wasn't great (certainly nothing like a college graduate makes), but as much as many Indians make at a full-time job.
After my sister told me about this, I checked up on the company out of curiosity. Terrible website, you could tell at a glance that this was borderline illegal/unethical/sleazy just from their website. But I've found several people who work for similar companies. Often they're bored housewives who don't mind working a couple of hours per day to earn some spending money.
One idea though - why not add one of those little "Are you a terrorist?" tick-boxes when you buy tickets?
:-)
Quoting from the second page of the US Department of State's current Form DS-156, Nonimmigrant Visa Application:
Do you seek to enter the United States to engage in export control violations, subversive or terrorist activities, or any other unlawful purpose? Are you a member or representative of a terrorist organization as currently designated by the U.S. Secretary of State? (Y/N)
That what you were looking for?
He's right; it's absolutely unintrusive. Perhaps their advertisers don't realise this? :-)
In earlier versions of Opera, the ads were noticeable. Now I find that I look at them perhaps once an hour at most.
Check Fast Forward and Rewind