HP boffin claims million-dollar maths prize

As Scott said...

...the answer is rather unlikely to be "yes" (otherwise there would be semi-godlike powers within our reach) but proving it may be as impossible to prove that the highest speed in this universe is exactly "c". It may just be a natural constraint: "Thou shalt not have an easy was to find a solution for problems that are easy to verify."

@LINCARD1000

I'll take a crack at that.

*Very* roughly it's the that all *know* ways of solving *some* problems are very "expensive" in some way (memory, time). The question is are their algorithms to solve one (or more) of these problems which are *radically* faster (but which we have not found yet) or is it impossible to solve the problems *any* faster.

The classic *real* world problem for this is Public Key Cryptography. One of the keys is derived by multiplying 2 *large* primes together. Factoring the result to identify *which* two is known to be *hard* IE very slow. It is *believed* there is *no* faster conventional way to factor it which can run on anything like what most people would call a computer (quantum "computers" are a different story).

If you can prove there is *no* faster way the system remains secure until quantum computers become readily available. Proving there *is* a faster way (which no one has found but does exist) would change the security landscape overnight.

Since PK crypto is used for cash transfers, credit authentication over the net and secure document transfer this would have *very* profound effects in the real world.

I think the safety of people's personal cash and privacy is a subject most people should take an interest in if they want to retain either or both.

http://www.scottaaronson.com/papers/npcomplete.pdf

"Even many computer scientists do not seem to appreciate how different the world would be if

we could solve NP-complete problems efficiently. I have heard it said, with a straight face, that a

proof of P = NP would be important because it would let airlines schedule their flights better, or

shipping companies pack more boxes in their trucks! One person who did understand was Gö̈del. In his celebrated 1956 letter to von Neumann (see [69]), in which he first raised the P versus NP question, Gödel says that a linear or quadratic-time procedure for what we now call NP-complete problems would have “consequences of the greatest magnitude.” For such an procedure “would clearly indicate that, despite the unsolvability of the Entscheidungsproblem, the mental effort of the mathematician in the case of yes-or-no questions could be completely replaced by machines.” But it would indicate even more. If such a procedure existed, then we could quickly find the smallest Boolean circuits that output (say) a table of historical stock market data, or the human genome, or the complete works of Shakespeare. It seems entirely conceivable that, by analyzing these circuits, we could make an easy fortune on Wall Street, or retrace evolution, or even generate Shakespeare’s 38th play. For broadly speaking, that which we can compress we can understand, and that which we can understand we can predict. Indeed, in a recent book [12], Eric Baum argues that much of what we call ‘insight’ or ‘intelligence’ simply means finding succinct representations for our sense data. On his view, the human mind is largely a bundle of hacks and heuristics for this succinct-representation problem, cobbled together over a billion years of evolution. So if we could solve the general case—if knowing something was tantamount to knowing the shortest efficient description of it—then we would be almost like gods. The NP Hardness Assumption is the belief that such power will be forever beyond our reach."

Pure

The pure maths of today will crop up in the physics of tomorrow and in engineering the day after that. In the 17th century, Newton's calculus might have seemed pointless to most people, but it is drilled into every engineering student today. Ditto Laplace transforms, the Cauchy–Riemann equations, Greens theorem in the plane etc. etc. etc, all of which some Reg readers use in their daily work, and others will remember fondly/vaguely from college.

@LINCARD1000

I think your question can be answered by a few examples. The problem is that at the time the pure maths is conceived, formulated and proven or conjectured (i.e. without current application) mathematicians probably have no way of knowing what, if any, the future applications will be.

E.G. I think that the problem of factorising products of pairs of large primes would probably have been considered an entirely theoretical area of maths without application prior to the development of public-key cryptography. Without this problem having been considered from a theoretical standpoint first, application for this purpose would not have been conceivable. Various other examples exist, including the use of complex numbers in electrical engineering. Group theory is an area of maths which I think also started as an entirely theoretical mind game yet which now has significant application areas in atomic and subsequently in molecular modelling. Graph theory was also pure maths which was later applied in network routing.

Go read "Godel, Escher, Bach"

Proving P != NP does not prove that sentience is somehow noncomputable. The two issues are totally distinct.

The existence of a form of reasoning that is fundamentally more powerful than mathematics and logic, as you suggest human intuition is, has consequences every bit as far reaching as if it were proven that P = NP. Fast, specialised heuristics do not a godlike intelligence make.

Savants (Idiot or otherwise) can be hugely mathematically gifted but they do not operate at some high level of reasoning, or they would be able to do arbitrarily complex calculations in constant time (instead of time increasing in proportion with, say, the size of the numbers involved).

@People who answered me & Andy Gibson

To those who answered my question, thank you :-) Always been good with the physical sciences and less so with the head-space pure mathematical ones. So, nothing particularly useful at the moment, but a bit further down the road it has implications for things like cryptography and the like... works for me.

Mr. Gibson - thank you for the laugh this afternoon... I'm with you, mate.

envy

Much like art, pure math has a world of beauty and insight and truth that is often hidden from those of us who are untrained. We look at a urinal standing upside down and labeled a fountain, or the fact that someone has derived a formula to calculate the n'th decimal of pi, scratch our heads a few times, and say, "Why on earth does anyone spend the time on this?" But what is really meant by that is, "Obviously someone appreciates this, and obviously it's important because there's all this ruckus about this, but I don't understand what the hell's going on well enough even to make an informed aesthetic judgment on way or the other. If I can't be in on the thing, then to hell with them all."

Where the breakdown of the analogy occurs is that pure math and all this weird, very abstract crap, often ends up being of immense practical importance. As a non-mathemetician, I defy any of the people poo-pooing pure math to name a single area of modern life that it hasn't shaped heavily. And while I'm at it, the question of whether P=NP is hardly the most "pure" of pure math problems-- the practical importance of an answer is well known-- an answer in the affirmative would surely spark a huge rush of research into finding polynomial solutions to NP-complete problems with a damn juicy reward for the lucky bastard to find and patent an answer.