Comment Re:The PCP Theorem (Score 5, Informative) 220
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
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
