Democratic Underground Latest Greatest Lobby Journals Search Options Help Login
Google

A Proof That P Is Not Equal To NP?

Printer-friendly format Printer-friendly format
Printer-friendly format Email this thread to a friend
Printer-friendly format Bookmark this thread
This topic is archived.
Home » Discuss » Topic Forums » Science Donate to DU
 
bananas Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 09:49 AM
Original message
A Proof That P Is Not Equal To NP?
http://www.newscientist.com/article/dn19287-p--np-its-b...

P ≠ NP? It's bad news for the power of computing
* 14:35 10 August 2010 by Richard Elwes

Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper titled simply "P ≠ NP".

This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute's seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.

<snip>

Complexity theorists have given a favourable reception to Deolalikar's draft paper, but when the final version is released in a week's time the process of checking it will intensify.


Followed one of the links from there to:
http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p... /

A Proof That P Is Not Equal To NP?
August 8, 2010
by rjlipton

<snip>

Deolalikars draft paper is herehe was kind enough to give me the pointer to his paper. For now please understand that this is a preliminary version. See the discussion by Greg Baker, who first posted on his paper.

<snip>

I suggest you look at his paper to see his own summary of his approach, and of course the details of his proof. At the highest level he is using the characterization of polynomial time via finite model theory. His proof uses the beautiful result of Moshe Vardi (1982) and Neil Immerman (1986):

<snip>


Printer Friendly | Permalink |  | Top
Recursion Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 09:59 AM
Response to Original message
1. Great news for cryptographers
Edited on Wed Aug-11-10 10:04 AM by Recursion
Bad news for cryptanalysts.

It's interesting, though: most of the profs I worked with who dabbled in this all leaned towards P=NP; IIRC a straw poll at some math conference or other had a large majority leaning towards =. Maybe people expected equality so much they didn't look as hard as they could have for a proof of inequality. But, probably not; the author's use of stochastic physical models is apparently quite novel (and interesting, since that's a field I'm into).
Printer Friendly | Permalink |  | Top
 
phantom power Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 12:44 PM
Response to Reply #1
2. That's remarkable -- everybody I ever studied with predicted P != NP.
(I always thought the smart money was on "!=" myself)
Printer Friendly | Permalink |  | Top
 
Recursion Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 01:01 PM
Response to Reply #2
3. Maybe I worked with optimists? NT
Printer Friendly | Permalink |  | Top
 
phantom power Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 01:36 PM
Response to Reply #3
4. LOL -- could be :-)
I recall some speculation that in the event somebody ever proved P = NP, it might or might not change the practical computing landscape much -- if (for example) one derived algorithms via the chains of known completeness proofs, you'd end up with polynomials of enormous exponent :-)

Particularly in light of the fact that good polynomial approximations are known for so many problems anyway.

Either way, I'm really looking forward to finding out if this proof holds up under review!

:toast:
Printer Friendly | Permalink |  | Top
 
Recursion Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Aug-11-10 01:42 PM
Response to Reply #4
5. I remember Knuth mentioning the bit about approximations
That it doesn't really matter what the answer is, because for non-marginal use cases we already have very good numeric or other-type approximations for most commonly-encountered traveling-salesman equivalents.
Printer Friendly | Permalink |  | Top
 
DU AdBot (1000+ posts) Click to send private message to this author Click to view 
this author's profile Click to add 
this author to your buddy list Click to add 
this author to your Ignore list Fri Nov 28th 2014, 07:43 AM
Response to Original message
Advertisements [?]
 Top

Home » Discuss » Topic Forums » Science Donate to DU

Powered by DCForum+ Version 1.1 Copyright 1997-2002 DCScripts.com
Software has been extensively modified by the DU administrators


Important Notices: By participating on this discussion board, visitors agree to abide by the rules outlined on our Rules page. Messages posted on the Democratic Underground Discussion Forums are the opinions of the individuals who post them, and do not necessarily represent the opinions of Democratic Underground, LLC.

Home  |  Discussion Forums  |  Journals |  Store  |  Donate

About DU  |  Contact Us  |  Privacy Policy

Got a message for Democratic Underground? Click here to send us a message.

© 2001 - 2011 Democratic Underground, LLC