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 previous 1-2021-4041-6061-68 next last
To: LibWhacker

Math U Philosophy = Bi polar dude.

I had a room mate just after college that was just about to finish a MS in math at Texas Tech. He disappeared one day. The finally called and said he checked himself into a mental hospital.


41 posted on 08/14/2010 10:15:53 PM PDT by ThomasThomas (Isn't enough always enough?)
[ Post Reply | Private Reply | To 1 | View Replies]

To: Mmogamer

Next weeks lotto number will be....


42 posted on 08/15/2010 6:11:14 AM PDT by Vaduz
[ Post Reply | Private Reply | To 2 | View Replies]

To: LibWhacker; Lonesome in Massachussets; decimon; neverdem; Ernest_at_the_Beach; AdmSmith; ...
There's an important alternative to Clarke's Third Law -- any mathematical proof sufficiently complicated is indistinguishable from magic." ;')
...the latest attempt to prove P ≠ NP -- otherwise known as the "P vs NP" problem -- seems to be running into trouble... 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... It is generally suspected that P ≠ NP. If this is so, it would impose severe limits on what computers can accomplish.

43 posted on 08/15/2010 6:46:24 AM PDT by SunkenCiv ("Fools learn from experience. I prefer to learn from the experience of others." -- Otto von Bismarck)
[ Post Reply | Private Reply | To 1 | View Replies]

To: SunkenCiv

To P or not to P: ay, there is the rub.


44 posted on 08/15/2010 7:08:45 AM PDT by decimon
[ Post Reply | Private Reply | To 43 | View Replies]

To: LibWhacker

I don’t understand why this is so hard P requires one operation.

NP requires at least two


45 posted on 08/15/2010 7:19:58 AM PDT by downwdims (It does not take a majority to prevail... but rather an irate, tireless minority)
[ Post Reply | Private Reply | To 1 | View Replies]

To: decimon; AdmSmith; bvw; callisto; ckilmer; dandelion; ganeshpuri89; gobucks; KevinDavis; ...
LOL! That reminds me...

· String Theory Ping List ·
Silly String Ordinance
· Join · Bookmark · Topics · Google ·
· View or Post in 'blog · post a topic · subscribe ·


46 posted on 08/15/2010 7:48:04 AM PDT by SunkenCiv ("Fools learn from experience. I prefer to learn from the experience of others." -- Otto von Bismarck)
[ Post Reply | Private Reply | To 44 | View Replies]

To: LibWhacker; Mmogamer; lefty-lie-spy
If P = NP then we can not trust that bank transactions are safe or trust cryptography, but we might find efficient algorithms for solving several computational problems. I hope that P is not equal to NP.

In order to even check a proposed solution it takes time to learn the technicalities, that is why there might be a correct proof at this page http://www.win.tue.nl/~gwoegi/P-versus-NP.htm but it is more likely that all are wrong.
47 posted on 08/15/2010 9:15:42 AM PDT by AdmSmith (GCTGATATGTCTATGATTACTCAT)
[ Post Reply | Private Reply | To 19 | View Replies]

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm


48 posted on 08/15/2010 9:16:38 AM PDT by AdmSmith (GCTGATATGTCTATGATTACTCAT)
[ Post Reply | Private Reply | To 47 | View Replies]

To: LibWhacker

As an engineer (not a scientist) I can’t help but feel more than a little sad every time I think of how the USA in 1984 literally threw away the pre-eminent institution of private basic research in the world....Bell Telephone Laboratories.

Had this institution and its corporate relationships and basic research been permitted to flourish as it had for decades, I have no doubt that this particular problem would have been solved years ago along with many others.

Candidly speaking I see a US government that has worked very hard and deliberative to destroy the once preeminent standing of the USA in research and manufacturing and exchange that capability so that a few crooks on Wall Street could make far too much money, and frankly I’m very ticked about it.

Today Bell Labs is just another typical corporate lab and it is owned by the French and Alcatel.

http://www.linfo.org/bell_labs.html


49 posted on 08/15/2010 9:39:45 AM PDT by apoliticalone
[ Post Reply | Private Reply | To 1 | View Replies]

To: patton

You just divided by zero.


50 posted on 08/15/2010 9:45:51 AM PDT by TheOldLady (Tagline left home again. Door hit it in the azz on the way out.)
[ Post Reply | Private Reply | To 16 | View Replies]

To: patton
Oops. Sorry for piling on, and sorry I didn't indicate <just kidding -- I know you know that> in my reply to #16.
51 posted on 08/15/2010 9:51:56 AM PDT by TheOldLady (Tagline left home again. Door hit it in the azz on the way out.)
[ Post Reply | Private Reply | To 40 | View Replies]

To: TheOldLady

I know - and you just passed the test. ;)


52 posted on 08/15/2010 9:57:11 AM PDT by patton (Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
[ Post Reply | Private Reply | To 50 | View Replies]

To: TheOldLady

It is quite alright - I still use that, on the rare occasion that I teach math classes.

It really drives the point home.

For a while, I also used it as an interview question - if the candidate can’t spot the error quickly, they are not suited for my job.


53 posted on 08/15/2010 10:00:02 AM PDT by patton (Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
[ Post Reply | Private Reply | To 51 | View Replies]

To: AdmSmith

Scott Aaronson on “P vs. NP for Dummies” http://scottaaronson.com/blog/?p=459


54 posted on 08/15/2010 10:34:50 AM PDT by AdmSmith (GCTGATATGTCTATGATTACTCAT)
[ Post Reply | Private Reply | To 48 | View Replies]

To: AdmSmith

Scott Aaronson on “P vs. NP for Dummies” http://scottaaronson.com/blog/?p=459


55 posted on 08/15/2010 10:34:59 AM PDT by AdmSmith (GCTGATATGTCTATGATTACTCAT)
[ Post Reply | Private Reply | To 48 | View Replies]

To: LibWhacker
Thanks for defending abstract studies ...wonder how many have heard of the Alexander Horned Sphere and alleph 0 and alleph 1.?

And then there is Mann's Hockey stick in regard to Global warming....

56 posted on 08/15/2010 11:00:05 AM PDT by Ernest_at_the_Beach ( Support Geert Wilders)
[ Post Reply | Private Reply | To 19 | View Replies]

To: patton

That was a pretty good brain teaser. I totally missed the divide by zero and was getting worried for a second that the universe didn’t make sense!


57 posted on 08/15/2010 11:07:37 AM PDT by Yardstick
[ Post Reply | Private Reply | To 16 | View Replies]

To: Yardstick

I blame it on Rocky - my HS math teacher.

Sadistic SOB. LOL!


58 posted on 08/15/2010 11:18:10 AM PDT by patton (Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
[ Post Reply | Private Reply | To 57 | View Replies]

To: patton

I was one of the first cohort of kids in my school district to be placed in the experimental “integrated math” curriculum track. Assignments often involved creating your own word problems. This was one of my first:

“Joe has three apples. Mary has no apples at all. Jealous of Joe’s good fortune, Mary multiplies her lack of apples by Joe’s three apples. How many apples does Joe have left.”

I didn’t like integrated math, much.


59 posted on 08/15/2010 11:29:17 AM PDT by Eepsy (www.pioacademy.org)
[ Post Reply | Private Reply | To 16 | View Replies]

To: Yardstick

OBTW, whenever a mathematician says “It should be obvious to the casual observer...”, here are a few interpretations:

1. I just pulled a fast one [which I did...]
2. It is beyond the scope of this class [I have no clue what I am doing...]
3. Then, a miracle occurs...[I have no clue what I am doing...]
4. Etc. Get a grad student to explain it, I have to hit the bar.


60 posted on 08/15/2010 11:33:24 AM PDT by patton (Obama has replaced "Res Publica" with "Quod licet Jovi non licet bovi.")
[ Post Reply | Private Reply | To 57 | View Replies]


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