# Maximum PC

 It is currently Wed Aug 20, 2014 11:09 pm

 All times are UTC - 8 hours

 Page 1 of 1 [ 20 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: P != NPPosted: Tue Aug 10, 2010 9:27 am
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Has anyone seen the proof? Does it look valid?

As I understand it, Deolalikar found an example of an NP problem (the Boolean satisfiability problem) that is not 'easily' solvable and therefore, !P.

However, the method that he used (very advanced stats and complexity maths) is beyond me.

Honestly, I was hoping for the opposite result .. if P = NP, the world of maths and CS would suddenly open up (if only in theory).

For the truly insane, here is the paper

Top

 Post subject: Re: P != NPPosted: Wed Aug 11, 2010 10:21 am
 SON OF A GUN

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Jipstyle wrote:
Has anyone seen the proof? Does it look valid?

As I understand it, Deolalikar found an example of an NP problem (the Boolean satisfiability problem) that is not 'easily' solvable and therefore, !P.

However, the method that he used (very advanced stats and complexity maths) is beyond me.

Honestly, I was hoping for the opposite result .. if P = NP, the world of maths and CS would suddenly open up (if only in theory).

For Gadget, here is the paper

Fixed

Top

 Post subject: Posted: Wed Aug 11, 2010 10:41 am
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven

I approve of this fix.

Actually, I've been reading as much as I can on this proof. I still can't speak to its validity, though. I can say that I'm pretty excited that this problem may have been solved (even if it isn't the result for which I was hoping).

Top

 Post subject: Re:Posted: Thu Aug 12, 2010 3:51 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
:lol:
I approve of this fix.

LOL... I haven't had time to sit down and read it yet, but from what I've heard about it, I'd probably be happy if I were able to follow half of the theorems proven in this paper! =)

Jipstyle wrote:
Actually, I've been reading as much as I can on this proof. I still can't speak to its validity, though.

The latest commentary that I've seen on the status of the paper suggests that the proof probably won't stand (as is), but it does use some new approaches that might provide valuable insight leading to additional work in the future.

Jipstyle wrote:
I can say that I'm pretty excited that this problem may have been solved (even if it isn't the result for which I was hoping).

Just curious, why do you want it to go P = NP instead?

Top

 Post subject: Re: P != NPPosted: Fri Aug 13, 2010 8:05 am
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Why? Because it'll cause a great deal of FUD around cryptography, but also because it means that there are answers to so many interesting questions.

Two very different reasons, I know.

I suppose I should say 'elegant, solvable (in human-time) solutions to so many interesting questions' rather than just answers.

Top

 Post subject: Re: P != NPPosted: Sat Aug 14, 2010 11:49 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
Why? Because it'll cause a great deal of FUD around cryptography

I assume that you're making this statement because of prime factorization, right? This is actually one of the problems that people aren't really too sure about which complexity class to place it. Proving P = NP might not matter all that much in this case. Of course, it mattering would spur on alternative encryption strategies and/or increased awareness of existing algorithms not based on prime factorization.

Jipstyle wrote:
solvable (in human-time) solutions to so many interesting questions' rather than just answers.

Well, it might be a bit less useful in the real-world than many of us have come to believe. First, there is the possibility that the solution is something like n^100, which would probably not prove to be very useful. Second, while many NP problems might be interesting to computer scientists and mathematicians, I'm not too sure that it will be viewed as warmly by the general media unless computers could suddenly perform tasks like language translation, speech recognition and object recognition perfectly. I don't believe that these tasks are actually in NP -- ditto for Chess, Go, and many other games. Of course, many of the computationally expensive tasks that people already perform, eg HDTV encoding, are presumably already in P and won't benefit from a stunning P = NP finding.

Anyways, I hope to get to the paper early next week. It should be interesting.

Top

 Post subject: Re: P != NPPosted: Thu Sep 09, 2010 10:18 pm
 Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
http://rjlipton.wordpress.com/2010/08/1 ... ars-proof/

Not a proof. Granted, I understand very little in the critique, but I'm quite sure a true proof would be recognized very very widely.

Top

 Post subject: Re: P != NPPosted: Fri Sep 10, 2010 11:15 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

Not a proof. Granted, I understand very little in the critique, but I'm quite sure a true proof would be recognized very very widely.

Yeah... by all accounts, it appears that the proof isn't going to hold up.

Did anyone else happen to see this though?

Beating A Forty Year Old Result: Hamilton Cycles

The idea that all NP problems may eventually be shown to have an exponential time worse-case is pretty darn interesting.

The speed up from 2^n to 1.657^n is actually quite a bit more significant than I would have thought initially...
Code:
CL-USER> (expt 2 20)    ;;for n = 20, the 40 year old algorithm...
1048576
CL-USER> (expt 1.657 20)       ;;is substantially slower than the new algorithm on even a small instance...
24347.25
CL-USER> (log 24347.25 20)    ;;which is roughly n^3.37 for this value of n... cool!  =)
3.371521
CL-USER>

Top

 Post subject: Re: P != NPPosted: Sat Sep 11, 2010 3:35 pm
 Northwood

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Why not just do 1000 problems of each and whichever holds out the most wins, heh.

Top

 Post subject: Re: P != NPPosted: Sun Sep 12, 2010 6:00 am
 SON OF A GUN

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Because that isn't a proof.

Top

 Post subject: Re: P != NPPosted: Sun Sep 12, 2010 12:27 pm
 Northwood

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
CrashTECH wrote:
Because that isn't a proof.

It was a joke

Top

 Post subject: Re: P != NPPosted: Sun Sep 12, 2010 12:30 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Prove it.

Top

 Post subject: Re: P != NPPosted: Sun Sep 12, 2010 8:33 pm
 Northwood

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Jipstyle wrote:
Prove it.

It was my problem, so I know how to solve it.

Top

 Post subject: Re: P != NPPosted: Fri Sep 17, 2010 7:05 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Why not just do 1000 problems of each and whichever holds out the most wins, heh.

Huh? I don't follow this proof... or joke.

Top

 Post subject: Re: P != NPPosted: Fri Sep 17, 2010 9:25 pm
 Northwood

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Dwood15 wrote:
Why not just do 1000 problems of each and whichever holds out the most wins, heh.

Huh? I don't follow this proof... or joke.

Proof it.

Top

 Post subject: Re: P != NPPosted: Sun Oct 24, 2010 9:33 am
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Here is an IBM research video discussing the history and failings of the proof.

I'm only about half-way through the video at the moment, but it seems to be worth a watch.

Top

 Post subject: Re: P != NPPosted: Fri Jan 21, 2011 12:25 pm
 SON OF A GUN

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Quote:
Vladimir Romanov has released what he claims is a polynomial-time algorithm for solving 3-SAT. Because 3-SAT is NP-complete, this would imply that P==NP. While there's still good reason to be skeptical that this is, in fact, true, he's made source code available and appears decidedly more serious than most of the people attempting to prove that P==NP or P!=NP. Even though this is probably wrong, just based on the sheer number of prior failures, it seems more likely to lead to new discoveries than most. Note that there are already algorithms to solve 3-SAT, including one that runs in time (4/3)^n and succeeds with high probability. Incidentally, this wouldn't necessarily imply that encryption is worthless: it may still be too slow to be practical.

http://science.slashdot.org/story/11/01 ... leased-PNP

Top

 Post subject: Re: P != NPPosted: Fri Jan 21, 2011 1:14 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Quote:
Even though this is probably wrong, just based on the sheer number of prior failures

Now there is some serious science reporting!

Top

 Post subject: Re: P != NPPosted: Fri Jan 21, 2011 10:43 pm
 Northwood

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
So the idea of this is to figure out ant prove that as a problem gets larger, it takes longer time to solve right? But then once you have your guess it can take a short time of checking if it's true.

I suppose that this is true if you're running your calculations from a single computer, on a single core/thread...

I come to think of the salesman problem, or a similar problem.

Quote:
Adleman's chief scientist, Nickolas Chelyapov, offered this illustration: Imagine that a fussy customer walks onto a million-car auto square and gives the dealer a complicated list of criteria for the car he wants.

"First," he says, "I want it to be either a Cadillac or a convertible or red." Second, "if it is a Cadillac, then it has to have four seats or a locking gas cap." Third, "If it is a convertible, it should not be a Cadillac or it should have two seats."

The customer rattles off a list of 24 such conditions, and the salesman has to find the one car in stock that meets all the requirements. (Adleman and his team chose a problem they knew had exactly one solution.) The salesman will have to run through the customer's entire list for each of the million cars in turn -- a hopeless task unless he can move and think at superhuman speed.

There is a case here that I can think of in which may not be P=NP but can come close, I do believe. But let me sleep on it haha.

Top

 Post subject: Re: P != NPPosted: Tue Jan 25, 2011 11:03 am
 8086

Joined: Sun Aug 29, 2004 5:13 am
Posts: 30
Ok, I reviewed the paper & came to this conclusion.
P = NP
They are opposites

Problem = No Problem

Have a good day.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 20 posts ]

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group