Free Republic
Browse · Search
General/Chat
Topics · Post Article

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-2021-4041-6061-68 next last

1 posted on 08/14/2010 7:57:40 PM PDT by LibWhacker
[ Post Reply | Private Reply | View Replies]

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.)
[ Post Reply | Private Reply | To 1 | View Replies]

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...)
[ Post Reply | Private Reply | To 2 | View Replies]

To: Mmogamer

P is not equal to not-P


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.")
[ Post Reply | Private Reply | To 2 | View Replies]

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)
[ Post Reply | Private Reply | To 1 | View Replies]

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!)
[ Post Reply | Private Reply | To 2 | View Replies]

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.)
[ Post Reply | Private Reply | To 2 | View Replies]

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)
[ Post Reply | Private Reply | To 1 | View Replies]

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.


9 posted on 08/14/2010 8:37:52 PM PDT by Sporaticus
[ Post Reply | Private Reply | To 7 | View Replies]

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.)
[ Post Reply | Private Reply | To 4 | View Replies]

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)
[ Post Reply | Private Reply | To 1 | View Replies]

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.")
[ Post Reply | Private Reply | To 11 | View Replies]

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.")
[ Post Reply | Private Reply | To 12 | View Replies]

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
[ Post Reply | Private Reply | To 8 | View Replies]

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.")
[ Post Reply | Private Reply | To 8 | View Replies]

To: LibWhacker
*ahem* I suggest they look really carefully at page 37.

That's all I'm sayin'.

17 posted on 08/14/2010 8:52:54 PM PDT by ClearCase_guy
[ Post Reply | Private Reply | To 1 | View Replies]

To: DrC

Is 0 odd or even?


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.")
[ Post Reply | Private Reply | To 15 | View Replies]

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!)
[ Post Reply | Private Reply | To 2 | View Replies]

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.)
[ Post Reply | Private Reply | To 18 | View Replies]


Navigation: use the links below to view more comments.
first 1-2021-4041-6061-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.

Free Republic
Browse · Search
General/Chat
Topics · Post Article

FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794
FreeRepublic.com is powered by software copyright 2000-2008 John Robinson