If P=NP, then mathematics as a field would be destroyed. | Hacker News Reader

If P=NP, then mathematics as a field would be destroyed.

claymath.org

14 pointsamichail23 comments

Stephen Cook writes:

For example, it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of reasonable length, since formal proofs can easily be recognized in polynomial time. Example theorems may well include all of the CMI prize problems. Although the formal proofs may not be initially intelligible to humans, the problem of finding intelligible proofs would be reduced to that of finding a recognition algorithm for intelligible proofs. Similar remarks apply to diverse creative human endeavors, such as designing airplane wings, creating physical theories, or even composing music. The question in each case is to what extent an efficient algorithm for recognizing a good result can be found. This is a fundamental problem in artificial intelligence, and one whose solution itself would be aided by the NP-solver by allowing easy testing of recognition theories.

That ignores the size of the polynomial, doesn't it? If the fastest polynomial-time proof finding algorithm is O(n^50), it's not going to do much good.

I don't think it would be so bad. There's be some constant factor or number where n^50 would always be less than, say n^n after that constant.

Yea, 51, but with n = 40 you are already at the number of atoms in the universe ~10^80. That would leave around 11^50 calculations per atoms in the universe, at 1,000,000 Ghz you are talking about 10^32 seconds which ~ 3 * 10^24 years. Or 10^15 = (1,000,000,000,000,000) times the current age of the universe.

For any calculable n, n^n is less than n^50. Ok, if computing power doubled every year, for the next 200 years we would still not be able do 50^50 calculations. But in 250 years of doubling each year it would be easy.

I don't understand how this can be true given Godel's Incompleteness Theorem. The theorem shows that not all true statements in the second order Peano axiomatic system for the integers can be formally proven by a computer. That is, no first order axiomatic system for the integers is rich enough to capture all true statements in the second order system.

The statement, '...allowing a computer to find a formal proof of any theorem which has a proof of reasonable length...' is where the problem lies. How does one determine which statements have proofs of reasonable length? I believe this is tied in with the Halting Problem. You just can't tell when something will be provable formally and when it can't. A proof of P=NP is not going to destroy mathematics.

Wait, he's saying that recognizing a proof in polynomial time makes finding a proof easy? The search space is exponential, and there's no adequate heuristic for a best-first search.

The quote is about the consequences of P = NP.

NP is the set of problems with solutions that are verifiable in polynomial time. If the problem size is n, imagine a non-deterministic Turing machine that can make one of 2 choices at each step. After n steps there are 2^n possible configurations of the machine, and your polynomial time verifier can check each of these configurations (in parallel, thanks to the non-determinism).

So there's n steps for the guessing and O(n^k) steps for the verification, so you've just been through an exponential search space in polynomial time.

That's why exponential search spaces are the bread and butter of NP. And also why many view P = NP as unlikely.

Absolutely not, and for far more reasons than I enumerate below.

The language used to encode the search space will be under constant development and expansion.

The creation of the axioms of any proof system is not a search problem.

Recognition of "meaningful" proofs will be extremely hard to automate. The checking of statements does not create mathematical theory, but it is the collection of related statementswhich do.

The search space is likely to be still much too large for proof systems to exhaustly enumerate all meaningful statements in any person's lifetime.

If mathematical statements could be easily checked, it would make mathematical study quite different. But likely much more interesting and fast paced.

I think it would make things more interesting. So many problems that would then be solvable in polynomial time.

Recall that primality testing was proved to be in P, O(n^6) via the AKS primality test, but in practice it's much too slow. So if something interesting is in P, but it's O(n^100), what good is that?

http://en.wikipedia.org/wiki/AKS_primality_test

well, it just brings us a couple of steps closer to an answer for "life, universe and everything"! :-)

Isn't it O(log n)? I guess computationally it may blow up if you are doing a significant number of operations.

It depends on how you measure n. The O(log^{6+\epsilon}(n)) quote on Wikipedia is for n being the number to be tested. This is "cheating"; inputs to an algorithm need to be measured by their length, and numbers are exponential in their length (i.e., the length of the number n is order log n for "reasonable encodings").

As an example, the knapsack problem with n objects and weight W is solvable in O(n*W) time, but it's known to be NP-hard. This doesn't prove P=NP, because W is exponential in its length. This is called a pseudopolynomial algorithm.

Ah got it. Thanks for the clarification.

Coincidental too since I just read about the AKS algorithm on Terrence Tao's blog. http://terrytao.wordpress.com/2009/08/11/the-aks-primality-t...

You could potentially use a run (or runs) through the O(n^100) problem to optimize approaches for smaller problems. If you were lucky that would ammortize the cost of the first run.

With a bit of luck you might also be able to come up with a scheme to generate optimal nonuniform circuits for smaller problem sizes, which would ammortize nicely if you had enough of the smaller instances to solve.

No, no, no Computer Science would be destroyed, not Mathematics.

A large portion of Computer Science is the study of algorithms including their complexity.

How can you say something is going to be destroyed by something that isn't even a question in the field?

If anything Mathematics is going to be improved by getting rid of some grunt work and giving way for some more creativity. Not to mention the theorems that if P=NP would come about which could be used for even further results.

All-in-all it's a win-win for Mathematics.

Mathematics and computer science are intertwined. And they would not be destroyed --- but merely closed (to a large extent) as a solved problem.

Algorithms and proofs have many interconnections. (You can usually abstract one out of the other with a bit of creativity. I.e. the classic proof for infinity of primes gives a basic algorithm for creating new primes.)

I didn't read the article because it's on scribd and I haven't installed flash on the new system yet.

But the headline sounds a bit too dramatic. We've been using and expanding applied mathematics for thousands of years. A proof of P=NP will not retro-actively make Roman aqueducts collapse, let alone destroy the infrastructure we're all using day-to-day. Which in turn means that whatever flawed assumptions have been made (and there's plenty of gray space to be found), the field of mathematics will not be destroyed.

QED. (Don't I feel smug).

[edit : I clicked on the scribd link initially but have now saved the PDF link for tomorrow's reading]

Click the title for the pdf.

Read a great short story by Charles Stross about this called 'Antibodies'. The notion was that a discovery like this would rapidly lead to strong AI. Never connected the two myself like that but now it seems obvious - AI is essentially an algorithms problem.

There is a guy called 'Musatov' on Sci.Math that is doing this very thing. The idea of mathematics being a representation of our line and line liberties is interesting in this regard.

I don't understand. The link is just the problem statement.

http://news.ycombinator.com/item?id=756761

Reply on news.ycombinator.com