Quantcast

Maximum PC

It is currently Tue Apr 15, 2014 10:10 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 20 posts ] 
Author Message
 Post subject: P != NP
PostPosted: Tue Aug 10, 2010 9:27 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24218
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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Wed Aug 11, 2010 10:21 am 
SON OF A GUN
SON OF A GUN
User avatar

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
  Profile  
 
 Post subject:
PostPosted: Wed Aug 11, 2010 10:41 am 
Java Junkie
Java Junkie
User avatar

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

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
  Profile  
 
 Post subject: Re:
PostPosted: Thu Aug 12, 2010 3:51 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Aug 13, 2010 8:05 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24218
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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sat Aug 14, 2010 11:49 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Thu Sep 09, 2010 10:18 pm 
Team Member Top 100
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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Sep 10, 2010 11:15 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sat Sep 11, 2010 3:35 pm 
Northwood
Northwood
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sun Sep 12, 2010 6:00 am 
SON OF A GUN
SON OF A GUN
User avatar

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


Top
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sun Sep 12, 2010 12:27 pm 
Northwood
Northwood
User avatar

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 :P


Top
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sun Sep 12, 2010 12:30 pm 
Java Junkie
Java Junkie
User avatar

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


Top
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sun Sep 12, 2010 8:33 pm 
Northwood
Northwood
User avatar

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


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


Top
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Sep 17, 2010 7:05 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Sep 17, 2010 9:25 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Sun Oct 24, 2010 9:33 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Jan 21, 2011 12:25 pm 
SON OF A GUN
SON OF A GUN
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Jan 21, 2011 1:14 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24218
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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Fri Jan 21, 2011 10:43 pm 
Northwood
Northwood
User avatar

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
  Profile  
 
 Post subject: Re: P != NP
PostPosted: Tue Jan 25, 2011 11:03 am 
8086
8086
User avatar

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. :wink:


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 1 guest


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

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group