My friend Ken Rose sent me a link to an article in the New Scientist. Vinay Deolalikar, a mathematician at Hewlitt-Packard labs, is about to publish a paper that proves there are problems in NP that are definitely not in P, which is an assumption people have been working with for some time but no one actually proved. He found a specific problem in the set of NP Complete problems, the one called n-SAT, cannot be solved in a "nice" amount of time. What this means is that if you come up with a method for solving all n-SAT problems, someone will be able to find a particular example of an n-SAT problem that will take effectively forever for your method to solve.
Here's a way to think of n-SAT. In a coalition of politicians, each member has a set of most important issues, but some people in the coalition have conflicting issues. For example, let's say one wants to increase funding for K-12 education, while another want to increase funding for college education. Let's say that given the education budget, only one of those two things can be done, so either choice will satisfy at least one member of your coalition and fail to satisfy another. Assuming that everybody has more than one pet issue, maybe you can make another budget choice on a different issue that will satisfy the people who lost on the education issue. Given any set of politicians each with their own set of priorities, can you make a budget that makes everyone happy at least once or is that impossible given the particular set of politicians? No matter how you think you can best solve this problem, there are some sets in a coalition where finding the right way to satisfy everyone is hard to find, or conversely, you will have to do a lot of work to prove that there is no way to satisfy everyone.
The subtitle of the New Scientist article is "It's bad news for the power of computing". My friend Ken saw the bright side immediately. Cryptography will always be possible, no matter how fast or big computers get. No encoding method is unbreakable, but if it takes a supercomputer hundreds of years or more to crack a code, then if I send you encrypted information using a very secure system, our secret is likely safe between us with a lifetime guarantee.
Deolalikar's paper is a draft, so maybe someone will yet find a hole in his argument, but if his work is solid, and the people who have read it so far think it is, he has solved one of the Millennium Prize problems, which means he's about to get a check for one MILLION dollars!
You are now encouraged to put your hands on your hips with arms akimbo and laugh your best villain's laugh.
Mwwa-HA! MOOAAHOHAHAHAHAHAAAAAAAAAAAH!
Congratulations to Dr. Deolalikar.
Tidak ada komentar:
Posting Komentar