Skip to comments.
Tide turns against million-dollar maths proof
NewScientist ^
| 8/13/10
| Jacob Aron
Posted on 08/14/2010 7:57:39 PM PDT by LibWhacker
Initially hailed as a solution to the biggest question in computer science, the latest attempt to prove P ≠ NP otherwise known as the "P vs NP" problem seems to be running into trouble.
Two prominent computer scientists have pointed out potentially "fatal flaws" in the draft proof by Vinay Deolalikar of Hewlett-Packard Labs in Palo Alto, California.
Since the 100-page proof exploded onto the internet a week ago, mathematicians and computer scientists have been racing to make sense of it.
The problem concerns the speed at which a computer can accomplish a task such as factorising a number. Roughly speaking, P is the set of problems that can be computed quickly, while NP contains problems for which the answer can be checked quickly. Serious hole?
It is generally suspected that P ≠ NP. If this is so, it would impose severe limits on what computers can accomplish. Deolalikar claims to have proved this. If he turns out to be correct, he will earn himself a $1 million Millennium prize from the Clay Mathematics Institute in Cambridge, Massachusetts.
(Excerpt) Read more at newscientist.com ...
TOPICS: Computers/Internet; Science
KEYWORDS: computer; factor; factoring; math; numbers; pnenp; proof; pvsnp; science; stringtheory
Navigation: use the links below to view more comments.
first 1-20, 21-40, 41-60, 61-68 next last
To: LibWhacker
What does this mean in english?
2
posted on
08/14/2010 8:02:51 PM PDT
by
Mmogamer
(I refudiate the lamestream media, leftists and their prevaricutions.)
To: Mmogamer
In plain english, it means there are weird but smart people who worry about things so I don’t have to...
3
posted on
08/14/2010 8:04:43 PM PDT
by
Mr Rogers
(When the ass brays, don't reply...)
To: Mmogamer
4
posted on
08/14/2010 8:05:38 PM PDT
by
patton
(Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
To: LibWhacker
Yeah, well, I exploded the proof the first day it came out. Guy forgot to carry the 5.
/obvious bunkum
5
posted on
08/14/2010 8:10:27 PM PDT
by
Titus Quinctius Cincinnatus
(The success of Darwinism was accompanied by a decline in scientific integrity. - Dr. Wm R. Thompson)
To: Mmogamer
Wikipedia has a pretty interesting article about it. I have no special knowledge about the subject. Never understood it. Never studied it.
6
posted on
08/14/2010 8:10:52 PM PDT
by
LibWhacker
(America awake!)
To: Mmogamer
This mean theoretical mathematicians have nothing better to do. There is no practical application for any of this, except to build into other proofs that may have some theoretical application. Its the same as the Busy Beaver and Ackerman sequences - sort of. I’m not an egg head, but know some of this stuff. Just pretend you never heard of this story, and the world will continue to move as it always has.
7
posted on
08/14/2010 8:11:52 PM PDT
by
lefty-lie-spy
(Stay metal. For the Horde \m/("_")\m/ - via iPhone from Tokyo.)
To: LibWhacker
100 pages? Wouldn't 0≠1 do? Where's my million?
8
posted on
08/14/2010 8:25:39 PM PDT
by
skr
(May God confound the enemy)
To: lefty-lie-spy
HELLO! Previously useless theoretical mathematics is always getting dusted off and being applied to new applications. University mathematics degrees are frequently titled and earned in ‘theoretical and applied mathematics’— b.s. m.s. phd.
Comment #10 Removed by Moderator
To: patton
P is not equal to not-P NP is nondeterministic polynomial time, not "not P."
11
posted on
08/14/2010 8:39:54 PM PDT
by
krb
(Obama is a miserable failure.)
To: LibWhacker
12
posted on
08/14/2010 8:40:18 PM PDT
by
JRios1968
(The real first rule of Fight Club: don't invite Chuck Norris...EVER)
To: krb
LOL - Ok. I wondered why is wasn’t “7P”
13
posted on
08/14/2010 8:43:22 PM PDT
by
patton
(Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
To: JRios1968
Apropos, I have actually seen mathematicians come to blows over a proof.
“Ok, 15-minute break - everybody go outside!”
14
posted on
08/14/2010 8:46:03 PM PDT
by
patton
(Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
To: skr
"Wouldn't 0≠1 do?" The proof is about SETS of numbers, e.g. The set of Odd numbers ≠ The set of Even numbers For this to be true, there cannot be any overlap between the 2 sets, which we know is true in the case of odd and even numbers simply because of how they are defined. But in the case at hand, if there were even one known counterexample where P=NP, no proof would be needed. But since no known counterexamples exist, the challenge is to prove rigorously that there cannot be any such examples. That may well require 100 pages. I trust that if any Freeper sent you $1 million on the basis of your "proof", you will return it...
15
posted on
08/14/2010 8:46:37 PM PDT
by
DrC
To: skr
Let A=B=1
Then, it follows that AA=AB
Hence, AA-BB=AB-BB
Thus, (A+B)(A-B)=B(A-B)
Therefore, it should be obvious to the casual observer, that A+B=B
And so A=0
QED, 1=0
16
posted on
08/14/2010 8:51:41 PM PDT
by
patton
(Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
To: LibWhacker
*ahem* I suggest they look
really carefully at page 37.
That's all I'm sayin'.
To: DrC
18
posted on
08/14/2010 8:53:38 PM PDT
by
patton
(Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
To: Mmogamer; lefty-lie-spy
I’ve been snooping around looking for applications. It’s considered very important for AI, quantum computing, cryptography, airline scheduling, etc. So it’s way up there in importance and not just some abstract intellectual exercise for pure mathematicians.
19
posted on
08/14/2010 9:03:01 PM PDT
by
LibWhacker
(America awake!)
To: patton
Yes!... :-)
Seriously, it’s even...
20
posted on
08/14/2010 9:05:53 PM PDT
by
Freeport
(The proper application of high explosives will remove all obstacles.)
Navigation: use the links below to view more comments.
first 1-20, 21-40, 41-60, 61-68 next last
Disclaimer:
Opinions posted on Free Republic are those of the individual
posters and do not necessarily represent the opinion of Free Republic or its
management. All materials posted herein are protected by copyright law and the
exemption for fair use of copyrighted works.
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson