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

http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf

by amichail • 17 years ago

14 23 17 years ago

amichail3• 17 years ago

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.

scythe• 17 years ago

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.

sown2• 17 years ago

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.

yequalsx• 17 years ago

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.

dspeyer• 17 years ago

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.

dave_au2• 17 years ago

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.

sidmitra2• 17 years ago

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

lsb• 17 years ago

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

sidmitra2• 17 years ago

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

dangoldin2• 17 years ago

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

dave_au2• 17 years ago

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.

brg• 17 years ago

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.

mpk• 17 years ago

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]

amichail3• 17 years ago

Click the title for the pdf.

travisjeffery• 17 years ago

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.

eru• 17 years ago

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.)

dejb• 17 years ago

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.

sown2• 17 years ago

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

amichail3• 17 years ago

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

mmmmmmm• 17 years ago

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.

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

Related Stories