» Math Proofs are Complex
Computer scientists believe that all problems solvable by a computer can be divided into two classes: easy (“Polynomial”) and hard (“Non-Polynomial”). The most important problem in computer science is to prove that these two classes are distinct and there isn’t some trick to make hard problems easy (“P ≠ NP“). Among other applications, if P = NP, then all encryption is broken.
A guy named Vinay Deolalikar has been passing around a 100-page paper that might be a proof that P ≠ NP. The paper passes the Ten Signs a Claimed Mathematical Breakthrough is Wrong checklist (scroll down). But, even moreso than previous famous proofs of Fermat’s Last Theorem and the Poincare Conjecture, Deolalikar’s proof spans so many subjects that there’s almost no one in the world who can understand the whole thing: “logic, statistics, graphical models, random ensembles, and statistical physics”.
As this Slashdot comment points out, that shouldn’t be a problem:
If he did his work right the proof of each individual [step] is a trivial thing; only their connection is non-trivial.
But personally, being trained in computer science and formal logic, and believing the realitivist theory of mathematics, I’ve always been suspicious of mathematical proofs. As this Slashdot comment explains, I don’t see why I should trust the peer review process to scale up to proofs of this complexity. I know mathematicians think I’m crazy, but I can’t help but think that mathematical proofs should be machine-verifiable. That way, as this Slashdot commenter jokes:
We’ll know that P != NP if it takes us less time to verify the proof as it took him to generate it.
Aren’t there solvable problems that are harder than NP?
I assume you’re simplifying for the non-expert readers, because although many of the common forms of encryption would be likely be broken (or, at least, breakable in polynomial time) if P=NP, there are forms of encryption that would not be broken by this. I’m confident that my one-time pad will not be cracked by technological means.
Don
10 Aug 10 at 1:21 pm
In general, when writing on a specialized topic, I assume that my readers will assume that I am dumbing it down. And in fact, the courses I took in school stopped before getting deep enough into complexity that I can say I really understand the class hierarchy. I use “P” and “NP” as shorthand for “problems that are reasonable on a deterministic Turing machine” and “problems that you really need a non-deterministic machine for” (see Wikipedia’s table).
I think the important thing that everyone should know about computers is that many problems are similar to other problems in difficulty and some problems are much harder than others. It’s hard to explain why complexity space matters, especially when you can go to Future Shop and buy a case load of external hard drives.
Besides, from what I gather all the active research is in quantum computational complexity now.
Jared
10 Aug 10 at 1:57 pm
It’s been a while, but isn’t quantum complexity often just O ( M / n ) where M is the non-quantum-order complexity of a problem?
Jack
10 Aug 10 at 3:30 pm
Quantum computers are probabilistic (in a certain way), so it’s always about what’s your chance of getting the right answer with a certain amount of effort.
Jared
10 Aug 10 at 4:08 pm
I know absolutely nothing about that!
You should write something on the subject, because I’m almost guaranteed not to be able to nitpick.
Don
10 Aug 10 at 5:11 pm
I know absolutely nothing about quantum computing, too.
Jared
11 Aug 10 at 9:17 am