Source code online books for professionals by professionals

check the solution to a decision problem, we’ll need more than a “yes” or “no”—we also require some kind of proof, or 
certificate (and this certificate is required to be of polynomial size). For example, if we want to know whether there is 
a path from s to t, a certificate might be the actual path. In other words, if you solved the problem and found that the 
answer was “yes,” you could use the certificate to convince me that this was true. To put it differently, if you managed 
to prove some mathematical statement, your proof could be the certificate.
The requirement, then, for a problem to belong to NP, is that I be able to check the certificate for any “yes” 
answers in polynomial time. A nondeterministic Turing machine can solve any such problem by simply guessing the 
certificate. Magic, right?
Well, maybe … You see, that’s the thing. We know that P is not magical—it’s full of problems we know very well 
how to solve. NP seems like a huge class of problems, and any machine that can solve all of them would be beyond 
this world. The thing is, in Algorithmica, there is such a thing as an NTM. Or, rather, our quite ordinary, humdrum 
computers (deterministic Turing machines) would turn out to be just as powerful. They had the magic in them all 
along! If P = NP, we could solve any (decision) problem that had a practical (verifiable) solution.
5
Actually, Impagliazzo’s definition of Algorithmica also permits some slightly different scenarios.
6
Note the “seems to.” We don’t really know whether P = NP, so the definition might actually be equivalent.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
232
Meanwhile, Back in Kansas …
All right, Algorithmica is a magical world, and it would be totally awesome if we turned out to be living in it—but 
chances are, we’re not. In all likelihood, there is a very real difference between finding a proof and checking  
it—between solving a problem and simply guessing the right solution every time. So if we’re still in Kansas, why should 
we care about all of this?
Because it gives us a very useful notion of hardness. You see, we have a bunch of mean-spirited little beasties  
that form a class called NPC. This stands for “NP-complete,” and these are the hardest problems in all of NP.  
More precisely, each problem in NPC is at least as hard as every other problem in NP. We don’t know if they’re 
intractable, but if you were to solve just one of these tough-as-nails problems, you would automatically have 
transported us all to Algorithmica! Although the world population might rejoice at not having to change its socks 
anymore, this isn’t a very likely scenario (which I hope the previous section underscored). It would be utterly amazing 
but seems totally unfeasible.
Not only would it be earth-shatteringly weird, but given the enormous upsides and the monumental efforts that 
have been marshaled to break just a single one of these critters, the four decades of failure (so far) would seem to 
bolster our confidence in the wager that you’re not going to be the one to succeed. At least not anytime soon.  
In other words, the NP-complete problems might be intractable (hard for computers), but they’ve certainly been hard 
for humans so far.