An HP mathematician claims to have solved one of computer science's thorniest problems and thus bagged a $1m prize for his million-watt brainpower. Fellow number-boffins, however, are saying otherwise. The million-dollar challenge, one of seven thrown down by the Clay Mathematics Institute (CMI) in its Millennium Prize series, …
Space the ultimate frontier?
I can't help but observe that physicists intent on identifying ever more subtle forms of matter tend to overlook the stuff that glues it altogether into coherency namely space (relatively matter free space in a 3D or even 4D sense) such as the vacuum.
I can do them.
"there are still five more million-dollar challenges out there"
Sheeze, I can't belive no-one had realised that before...
Where you went wrong
42 42 42 42
There. There were five cheques: you now get one, I get the other four!
no, you don't...
... he gets one big chunk of cheese, and you get four big chunks of cheese, courtesy of the white mice. Unfortunately for both of you, the five remaining million-dollar prizes are NOT for the ultimate answer, so there's an infinite improbability that either of you will cash one of them... Good try, though... I'll go and carve some fjords now...
fascinating if valid
This was brought up in my comp sci classes, and has been a problem people have been noodling over since at least the 1930s. The intuition is "no" but the proof, well, very difficult. And if the answer were proven "yes" it meant there were serious shortcuts to certain algorithms as yet to be found. (this doesn't prove there aren't shortcuts but means there don't have to be.)
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."
forgotten some classes?
Since the 1970s, you mean. Gödel came up with the basic idea in a private letter in 1956, but it was only in 1971 that Steve Cook defined P and NP and posed the problem.
Looks like I'll have a long day reading through my college TheorCompSci notes tomorrow.
pure maths ptui
the trouble as I see it is that some areas of pure maths are inherently theoretical without a realistic anchor in the practical world;
P vs NP is one such area - hence it's really a question of phrasing the 'proof' in terms that'll persuade people, given currently accepted norms, rather than strictly proving it from first principles;
similarly in some ways the universality of turing machines, albeit more instinctively recognizably correct, involves far more hand-waving than so-called 'pure' mathematicians ever really admit
hence the challenge - is the 'proof' such a heap of waffle that it could prove a falsehood - is entirely well-founded, in fact the instinctive feeling is that all that could possibly be proved is that P != NP can't be conclusively proved :-)
Now I suppose I shall have to try to read the paper even so :rolleyes:
Who gives a rat's ass if it has a "realistic anchor in the practical world"? Does everything have to?
Mathematics can be applied to just about anything precisely /because/ it has nothing to do with reality. It is a mere convenient coincidence that it is useful. If you want a system of logic that transcends reality, you have to let people investigate math for math's sake. When you try to railroad any academic discipline toward things that are apparently practical, what you get is Lysenkoism. Did wonders for Russian biology--good thing they focused on practical crop research instead of giving attention to those dumb genticists who did nothing but putz around with flies. Nothing'll ever come of that!
Mathematicians do this stuff for fun. If they didn't, why'd Perelman turn down a million dollars and a Fields medal? He wasn't in it for the money. He just wanted to know whether every simply connected compact manifold was isomorphic to a 3-sphere. He got a kick out of figuring it out. In fact, he appears to have quit professional mathematics because he's tired of being pestered about it.
Does the fact that he works for HP figure in this?
I can see the headlines...
"P ≠ NP solved by HP"
Strong claims need strong evidence
The mere length (116 pages) of the paper that allegedly proves the result is enough to cause scepticism. Unlike what most people think, mathematical proofs are not just exact formal notation that can be checked by a computer, so some call mathematical proofs a social phenomenon: If sufficiently many respected mathematicians say that they believe the proof to be O.K., it is deemed to be so, but otherwise not. If the proof is for a long-unproven hypothesis, the number and respectability of these supporters is larger than if you prove an unimportant theorem that needed proof mainly because noone had looked at the problem before.
But getting a large number of respected mathematicians to check a 116-page paper takes a long time, so until this happens, I'm sceptical. It took years for Wiles proof of Fermat's last theorem to be generally accepted. It was 108 pages long, btw.
All a case of scale and priorities
I finally got around to painting the kitchen yesterday, that's achievement enough for me, for one week!
Had a quick read through
It isn't your average crank stuff, so it's a real attempt, but I doubt it's valid. We'll see, of course.
Also, Perelman didn't earn $1m, but he refused it.
So has he now proved
that there are no odd perfect numbers, or that it would take 7.5 million years (or more) to answer the question?
Re:I can do them
Sorry, but Douglas Adams had prior art on that answer.
...how exactly does this help HP's bottom line? I'm sure if I went away and spent days/weeks/months trying to figure out some obscure "problem" I have another problem - no job.
Not being a number boffin, I have difficulty in understanding the importance of finding solutions to some of these more abstract mathematical concepts... Aside from the ones that have tie-ins to physics as I understand that solving some of these can lead to all sorts of new developments or understanding of the physical universe.
But what, prey tell, is the real world benefit to solving some of these strange questions? Other than "because it was there" kind of mindset, what practical benefit to humanity is there if these pure-mathematical questions are proved/disproved?
Not trying to flame or cast aspersions, I am genuinely curious.
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.
"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 ), 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 , 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."
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.
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.
lets wait couple some more 1000 ears...
... when the maths would be even more advanced and let the future people worry about the solution.
Maybe we do not have the required tools to solve this puzzle yet, like previous math-lovers did not have ours. Could one actually ( based on current historical knowledge ) predict / estimate how log to wait for a solution of a problem in maths given this problem's complexity ? And since the problem is about the complexity itself does my previous question make sense at all ?
Comes to mind if its the answer or the question that advances out knowledge more. We are waiting maybe for different approach to the problem and a different question ... and don't look at me just 'cos I know how to spent a million doesn't mean I know how to earn it.
And when Monsters mentioned Shakespeare and Einstein me wonders: if we were to form a mathematical description of their DNA and then apply it to their lives formalized in further equations would they produce anything else than their actual works we know now. So if we are able to do that we could extend the lives of said people and see what else they would produce, something like Genie-Sim.
Again if we can do that we can simulate reality and looking at the current news and state of affairs it is all we are ever trying to achieve.
ah pure mathematicians
I guess since the new math coming out String Theory has largely dried up (theory still largely stands last I hear but need more empirical data for the mathematicians to move forward) the math boffins need something to do to pay the mortgage. Thank God we have a rare set of individuals that not only can work with the best mathematicians in the world but also can come back to the real work and work with the best applied people as well. Ed Witten I will buy you a pint if I ever meet you.
"I guess since the new math coming out String Theory has largely dried up"
Homological mirror symmetry? Not really dried up as far as I can tell...
Perelman _refused_ the prize.
Paris, because she does not care about money too.
Ian Stewart's explanation of how to play Minesweeper is wrong. Can I have a million?
Prove it? :)
Perelman never cashed $1m
Perelman actually refused the $1m prize. http://www.times.spb.ru/index.php?story_id=31837&action_id=2
OK here goes...
But I've only had one cup of tea this morning...
Essentially the problem seems to be looking for a mathematical shortcut. P problems are like E=MC squared. Easy. Fill in the numbers and grab a calculator. NP problems take longer to work out, the more data you have. So, if you have a very big minesweeper grid or a very long encryption key, you need a very big computer and it will take a much longer time. Now if there was a shortcut in maths for cracking a very long key, that is a different algorithm, your internet security would be, to use the technical term, toast. So if P=NP, maths can guess. Or to put it another way, can maths make a guess, using what we might call intuitive reasoning? So really they want to know if maths can emulate human intuition. If P=NP then you could replicate human intuition and make a proper replicant.
I'd posit that the answer is 'no' and that P<>NP because intuitive reasoning is fundamentally different from mathematical reasoning. So full AI cannot happen. You need processors that work so quickly, they can test every possibility and choose, with the appearance of AI. We can pretend that maths can do this sort of thing with fuzzy logic, but fuzzy logic is approximating without intuition. It is probability, smoke and mirrors. It certainly isn't accurate enough to be acceptable amongst chaps who work with grown up algorithms, who may well look down on fuzzy logic types and scorn them in private.
Now the fun bit. Because you cannot mathematically quantify the concept of intuitive reasoning (the way we think and make decisions) you cannot express a proof for this problem in purely mathematical terms (one of the variables being mathematically inexpressible).
This is not to suggests that humans have some special quality beyond science, but that we reason using a technique that differs fundamentally from the way algorithms work in mathematics. It's like trying to convey something to someone in a language that has no words for it and who has no conception of it.
So computers cannot 'cheat' and think intuitively the way we do, although they can pretend to if they can work quickly enough, but people can go some way to emulating computers. At the far end of the autism spectrum, there are folk who can process data far more rapidly than we can, but can have difficulty with the more 'analogue' aspects of day to day life. Which may suggest that human beings typically operate with an intuitive system of reasoning to accommodate emotional interaction.
So, N<>NP and whilst two sides of an algorithm can equate, they will not then express their love for each other.
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).
Quick and dirty example.
"This is not to suggests that humans have some special quality beyond science, but that we reason using a technique that differs fundamentally from the way algorithms work in mathematics. It's like trying to convey something to someone in a language that has no words for it and who has no conception of it."
Like trying to teach Zero to an ancient Roman. Or the concept of cellular pathogens prior to the advent of microscopy.
Like trying to teach Zero to an ancient Roman
But why would you want to? Far better would be to keep him in the dark and contract yourself out to him for any multiplication or long division sums he needs to carry out in his work.
what a difference
In the comments on this article and the ASA "f**k" one. Just goes to show what a diverse readeership we have.
And just in case you're not sure which camp I'm in - fookity fookity fuck. Twat. Piss. Balls.
@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.
@Jon Smith 19
Factoring numbers is not NP-complete. Quantum computers are able to factor numbers in polynomial time. But, Quantum computers can not handle NP-complete problems. It follows that factoring is not NP-complete. So your example is wrong.
Factoring and NP
Factoring is indeed not believed to be NP complete. But it certainly lies in NP, since if I gave you a factor you could check whether my factor was correct very fast.
So if P=NP then factoring would be easy and factoring based crypto (indeed almost all practically deployed crypto) would be broken.
But if P<>NP we still have no idea whether factoring is easy or hard.
I see a lot of comments that are whining about how pure mathematics isn't practical. Tell me, all you folks who are whining about that: Do you have any practical reason for complaining about it?
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.
Pure mathematics? Not quite
The question of P vs. NP stands quite firmly in the domain of APPLIED mathematics, thankyouverymuch. Pure mathematicians do not deal with this kind of dirty Turing machines-type questions. Why, it is almost computer science!
Why did I read all that?
My head hurts now.
No one made me read it...
Ah...The Sanity Clause.
QUOTE < the HP boffin's proof must first pass "a sanity test." >
And as Chico Marx said: "You can't fool me, there ain't no Santa-de-Claus"
I'm rubbish at maths
Although I did know what an NP problem is. But that aside, it seems to me that proving something is not possible is a hell of a lot easier than proving it IS possible.
All he's done is prove that he can't do it. How do we know that somebody else won't come along next year with a perfect solution? Rather unlikely but that's not the point.
Proving the Negative.
This is actually exceedingly difficult because the proof is not valid unless it accounts for ALL possible cases. In other words, a negative proof MUST show that no matter what you attempt, you will fail. Of course, some will say, "You can't prove a negative," but you can...by showing that the positive universally creates logical inconsistencies. That's the idea of a proof by contradiction (the Halting Problem explanation is a classic example).
Put me down for a fiver
Scott Aaronson from MIT(quoted in the story) is betting $200,000 that the proof is wrong.
"If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000."
The comment that alludes to the metaphor of human reasoning, would be a way of proving P=NP - that is, for sufficiently large c, NP-complete is O(n^a)
How I prove it, very simply:
the brain is composed of 100Bn neurons
Every neuron is equivalent to an individual turing machine that produces a result in all of its finite number of axons, as a function of state + input in the dendrites - as far as we know
Hence a statement to the effect that the human brain is capable of solving NP-complete in polynomial time is a statement that it is possible to construct a neural network of turing machines that would solve NP-complete in polynomial time - ie P = NP
As for the pure mathematicians resorting to ad hominem tactics to defent their hobby, you people need more fresh air :-D
'there are some pure maths domains that are apparently entirely theoretical, such as "how to prove P != NP"'
from some kind of sweeping statement such as
"no pure maths has ever had a connection to reality"
that would clearly be misleading
NP = N is true, IF
N = 1.