P≠NP
Moderators: Zamfir, Hawknc, Moderators General, Prelates
P≠NP
A researcher's published a paper claiming to prove that P≠NP. It hasn't been peerreviewed yet, but it looks promising.
http://www.scribd.com/doc/35539144/pnp12pt
Anyone want to read the proof and find flaws? :P
http://www.scribd.com/doc/35539144/pnp12pt
Anyone want to read the proof and find flaws? :P
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffercait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.
 TheGrammarBolshevik
 Posts: 4878
 Joined: Mon Jun 30, 2008 2:12 am UTC
 Location: Going to and fro in the earth, and walking up and down in it.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
When it appears here: http://www.scottaaronson.com/blog/
then ill believe it. Anyway, its pretty odd to me that he published it on scribd, not the arxiv or anything like that.
then ill believe it. Anyway, its pretty odd to me that he published it on scribd, not the arxiv or anything like that.

 Posts: 669
 Joined: Mon Dec 17, 2007 8:40 am UTC
Re: P≠NP
BlackSails wrote:When it appears here: http://www.scottaaronson.com/blog/
then ill believe it. Anyway, its pretty odd to me that he published it on scribd, not the arxiv or anything like that.
According to the reddit thread, it wasn't the author who uploaded it. He initially emailed it to the top people in complexity theory for sanity checking, and it got forwarded on from there.
It's about time someone cracked another Millenium Prize problem...
 CorruptUser
 Posts: 10495
 Joined: Fri Nov 06, 2009 10:12 pm UTC
Re: P≠NP
If true, [angry_sobbing]why?[/angry_sobbing]
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
CorruptUser wrote:If true, [angry_sobbing]why?[/angry_sobbing]
It would be very terrible if P were to equal NP.
 CorruptUser
 Posts: 10495
 Joined: Fri Nov 06, 2009 10:12 pm UTC
Re: P≠NP
Wait, if P ≠ NP, that means solvable problems may take an exponentially long time to, err, solve, but P = NP means that problems can be quickly solved, leading to solutions to the travelling salesman type problem, and more importantly, the "which combination of atoms and molecules creates an enzyme that breaks down only the AIDS virus" type problems. Or do I have it backwards, where P = NP means not quickly solvable?
Re: P≠NP
CorruptUser wrote:Wait, if P ≠ NP, that means solvable problems may take an exponentially long time to, err, solve, but P = NP means that problems can be quickly solved, leading to solutions to the travelling salesman type problem, and more importantly, the "which combination of atoms and molecules creates an enzyme that breaks down only the AIDS virus" type problems. Or do I have it backwards, where P = NP means not quickly solvable?
i think p = np means problems with answers that are verifiable in polynomial time take polynomial time to solve, and that p=/=np means they can take more than polynomial time
the practical significance of p versus np comes from cryptology though, because if p=np, then that field is bascially finished.
Last edited by PeterCai on Mon Aug 09, 2010 5:33 am UTC, edited 1 time in total.

 Posts: 92
 Joined: Sat May 01, 2010 8:59 am UTC
 Location: Brisbane, Australia
Re: P≠NP
CorruptUser wrote:Wait, if P ≠ NP, that means solvable problems may take an exponentially long time to, err, solve, but P = NP means that problems can be quickly solved, leading to solutions to the travelling salesman type problem, and more importantly, the "which combination of atoms and molecules creates an enzyme that breaks down only the AIDS virus" type problems.
That's right. I assume BlackSails calling it a "bad thing" refers to the fact that modern cryptography relies on there being computationally difficult problems. Whether the benefits of cryptography outweigh the benefits of fast simulation of physical systems is something I'm not sure about (I had an ethical dilemma about wanting to do quantum computing research for this very reason).
edit: ninja'd
 CorruptUser
 Posts: 10495
 Joined: Fri Nov 06, 2009 10:12 pm UTC
Re: P≠NP
I think I'd be more worried about P = NP leading to sentient computers, given tasks of optimizing production, that decide that fleshy humans are too inefficient and must be 'recycled' for the optimal use of proteins.
If push comes to shove, we can always disconnect the computers with sensitive information from the interblags and transfer information by hand, or something.
If push comes to shove, we can always disconnect the computers with sensitive information from the interblags and transfer information by hand, or something.
Last edited by CorruptUser on Mon Aug 09, 2010 5:38 am UTC, edited 4 times in total.
 TheGrammarBolshevik
 Posts: 4878
 Joined: Mon Jun 30, 2008 2:12 am UTC
 Location: Going to and fro in the earth, and walking up and down in it.
 netcrusher88
 Posts: 2166
 Joined: Mon Mar 26, 2007 4:35 pm UTC
 Location: Seattle
Re: P≠NP
Consider a cryptographic hash, an NP but not P problem (I think). A hash can be verified as belonging to a piece of data in polynomial time. Theoretically a piece of data that can be hashed through the same algorithm to the same hash cannot be found in polynomial time (especially not one that does what the original data is expected to do). This is what makes cryptographic hashes secure. P=NP would break them, along with PKI (which depends on factoring being really hard and expensive) and various encryption schemes.
There are ways of cheating at some NP problems, like when you store a password hashed you can use a dictionary attack. For expensive hash operations (the longer a hash on a password takes to process the more secure it is, and however WPAPSK works is computationally expensive and salted with the ESSID or something) you can pregenerate rainbow tables that contain computed hashes for dictionary words but it's still just a dictionary attack. So you attach a random salt to a long nondictionary password before you hash it (and use nondictionary ESSID and key on your wifi) to make dictionaries worthless.
There are ways of cheating at some NP problems, like when you store a password hashed you can use a dictionary attack. For expensive hash operations (the longer a hash on a password takes to process the more secure it is, and however WPAPSK works is computationally expensive and salted with the ESSID or something) you can pregenerate rainbow tables that contain computed hashes for dictionary words but it's still just a dictionary attack. So you attach a random salt to a long nondictionary password before you hash it (and use nondictionary ESSID and key on your wifi) to make dictionaries worthless.
Sexothermic
I have only ever made one prayer to God, a very short one: "O Lord, make my enemies ridiculous." And God granted it. Voltaire
They said we would never have a black president until Swine Flu. Gears
They said we would never have a black president until Swine Flu. Gears
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: P≠NP
The NP problem that is of most interest to me is the SAT problem. Basically, if I give you an expression in first order predicate logic, can you determine if there is an assignment of true or false to the variables such that the expression evaluates to true? This is the problem you need to solve to verify that a computer chip does what it is designed to do (the expression is "does this chip ever do what its not supposed to?" but written in first order logic).
If this guy is right we'll always be falling behind on verifying that the chips we use do what they should do... which maybe isn't a big problem, but is one that I find interesting.
If this guy is right we'll always be falling behind on verifying that the chips we use do what they should do... which maybe isn't a big problem, but is one that I find interesting.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 669
 Joined: Mon Dec 17, 2007 8:40 am UTC
Re: P≠NP
jestingrabbit wrote:The NP problem that is of most interest to me is the SAT problem. Basically, if I give you an expression in first order predicate logic, can you determine if there is an assignment of true or false to the variables such that the expression evaluates to true? This is the problem you need to solve to verify that a computer chip does what it is designed to do (the expression is "does this chip ever do what its not supposed to?" but written in first order logic).
If this guy is right we'll always be falling behind on verifying that the chips we use do what they should do... which maybe isn't a big problem, but is one that I find interesting.
SAT seems to be the most intuitively powerful of the NPcomplete problems, even though they're all technically equivalent. I think it was also the first one to be proven NPcomplete, since any problem in NP ("is there an <X> satisfying polynomially checkable predicate <P>?") can be formulated as "is there a binary input satisfying this particular circuit?" simply by building a circuit that implements <P>.

 Posts: 524
 Joined: Thu Nov 08, 2007 3:36 am UTC
Re: P≠NP
bosonicyouth wrote:That's right. I assume BlackSails calling it a "bad thing" refers to the fact that modern cryptography relies on there being computationally difficult problems. Whether the benefits of cryptography outweigh the benefits of fast simulation of physical systems is something I'm not sure about (I had an ethical dilemma about wanting to do quantum computing research for this very reason).
It's not like destroying encryption would cause the collapse of the world economy of something.
 fjafjan
 THE fjafjan
 Posts: 4766
 Joined: Fri Oct 06, 2006 12:22 pm UTC
 Location: Down south up north in the west of eastern west.
 Contact:
Re: P≠NP
How would P = N*P destroy encryption?
It would prove that yes, there should exist some algorithm that can decrypt as fast as can be decoded, but whether this algorithm exists or is possible to implement today is another matter. I mean the prime case is of course RSA encryption which can be broken in polynomial time by Shor's Algorithm. But that requires a quantum computer, which we don't have. What is there to say other encryption methods would not be similar?
It would prove that yes, there should exist some algorithm that can decrypt as fast as can be decoded, but whether this algorithm exists or is possible to implement today is another matter. I mean the prime case is of course RSA encryption which can be broken in polynomial time by Shor's Algorithm. But that requires a quantum computer, which we don't have. What is there to say other encryption methods would not be similar?
//Yepp, THE fjafjan (who's THE fjafjan?)
Liza wrote:Fjafjan, your hair is so lovely that I want to go to Sweden, collect the bit you cut off in your latest haircut and keep it in my room, and smell it. And eventually use it to complete my shrine dedicated to you.
Re: P≠NP
You know, on my computer the ≠ sign in the title looks a lot like the = sign. I got through half a bottle of paracetamol before I noticed the difference.
Chuff wrote:I write most of my letters from the bottom
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
http://scottaaronson.com/blog/?p=456
He might be wrong, but he is basically the god of computational complexity.
He might be wrong, but he is basically the god of computational complexity.
 Godskalken
 Posts: 159
 Joined: Wed May 14, 2008 3:29 pm UTC
Re: P≠NP
If P=NP, that doesn't necessarily mean anything else than that there is an algorithm solving problems now believed to be NP in O(n to the grahams number) time, or something. I can't see that ruining cryptography, or even being very useful (though undoubtedly very interesting) in the foreseeable future.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
Godskalken wrote:If P=NP, that doesn't necessarily mean anything else than that there is an algorithm solving problems now believed to be NP in O(n to the grahams number) time, or something. I can't see that ruining cryptography, or even being very useful (though undoubtedly very interesting) in the foreseeable future.
In general, polynomial time algorithms have small exponents.
 Godskalken
 Posts: 159
 Joined: Wed May 14, 2008 3:29 pm UTC
Re: P≠NP
BlackSails wrote:Godskalken wrote:If P=NP, that doesn't necessarily mean anything else than that there is an algorithm solving problems now believed to be NP in O(n to the grahams number) time, or something. I can't see that ruining cryptography, or even being very useful (though undoubtedly very interesting) in the foreseeable future.
In general, polynomial time algorithms have small exponents.
Well, until there was a deterministic algorithm of order < n^3 for solving consistent linear systems, one thought such an algorithm would revolutionize linear algebra. It surely didn't.
 Jessica
 Jessica, you're a ...
 Posts: 8337
 Joined: Tue Oct 23, 2007 8:57 pm UTC
 Location: Soviet Canuckistan
Re: P≠NP
I <3 the sanity checking process of mathematical proof. It's just awesome.
doogly wrote:On a scale of Mr Rogers to Fascism, how mean do you think we're being?
Belial wrote:My goal is to be the best brain infection any of you have ever had.
 Jessica
 Jessica, you're a ...
 Posts: 8337
 Joined: Tue Oct 23, 2007 8:57 pm UTC
 Location: Soviet Canuckistan
Re: P≠NP
It would stop people from trying to prove otherwise?
doogly wrote:On a scale of Mr Rogers to Fascism, how mean do you think we're being?
Belial wrote:My goal is to be the best brain infection any of you have ever had.
Re: P≠NP
The way it was proven could develop some interesting new fields?
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffercait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: P≠NP
joshz wrote:The way it was proven could develop some interesting new fields?
Yeah, it should allow us to analyse the complexity of algorithms in a new way, or at least that's a likely outcome.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
I believe there are several other seperations of complexity classes that are only true if P=NP (or if P!=NP)
Re: P≠NP
It sounds like he doesn't think the proof is right, which is always a good bet.BlackSails wrote:http://scottaaronson.com/blog/?p=456
He might be wrong, but he is basically the god of computational complexity.
However, I would like to add that If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, <REDACTED>, will personally supplement his prize by the amount of twenty homemade chocolate chip cookies. Because if you prove P≠NP, then you shouldn't have to make your own cookies.
Re: P≠NP
Jessica wrote:It would stop people from trying to prove otherwise?
But some people are still trying to prove that 0.999... ≠ 1 <_<
oh yes, I went there.

 Posts: 4008
 Joined: Fri Oct 12, 2007 5:37 am UTC
 Location: San Antonio, Tx
 Contact:
Re: P≠NP
Osha wrote:Jessica wrote:It would stop people from trying to prove otherwise?
But some people are still trying to prove that 0.999... ≠ 1 <_<
oh yes, I went there.
infinitesimals FTW!
 b.i.o
 Green is the loneliest number
 Posts: 2519
 Joined: Fri Jul 27, 2007 4:38 pm UTC
 Location: Hong Kong
Re: P≠NP
fjafjan wrote:How would P = N*P destroy encryption?
It would prove that yes, there should exist some algorithm that can decrypt as fast as can be decoded, but whether this algorithm exists or is possible to implement today is another matter. I mean the prime case is of course RSA encryption which can be broken in polynomial time by Shor's Algorithm. But that requires a quantum computer, which we don't have. What is there to say other encryption methods would not be similar?
First, it's NP, not N*P. We're dealing with complexity classes, not multiplication, which is an important difference here .
P is a subset of NP. So for someone to prove that P=NP, they'd have to prove that NP is also a subset of P. That is, that there's a polynomialtime reduction from any problem in NP to a problem in P. And, importantly here, P and NP are complexity classes relating to computation on normal Turing machines (basically the computers we're using, except that our computers don't have infinite storage). Shor's Algorithm, by contrast, is in the complexity class BQP (problems that can be solved in polynomial time on a quantum computer with a low error probability), but not P, and that's the reason we can't implement it on a normal computer. If P=NP, then we'd be able to break RSA (and other kinds of) encryption on normal computers.
It's true though that a proof of P=NP doesn't necessarily give us easy solutions to hard problems for freeit just means that those solutions do exist.
Last edited by b.i.o on Tue Aug 10, 2010 5:16 am UTC, edited 1 time in total.
Re: P≠NP
Aren't there already algorithms for which, if P=NP, could construct the algorithm for any NP problem? That is, they rephrase any NP problem as some particular NP problem that was solved (SAT is the textbook one, isn't it?) and use the "fast" algorithm for it to obtain a fast result for the other problem?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

 Posts: 669
 Joined: Mon Dec 17, 2007 8:40 am UTC
Re: P≠NP
WarDaft wrote:Aren't there already algorithms for which, if P=NP, could construct the algorithm for any NP problem? That is, they rephrase any NP problem as some particular NP problem that was solved (SAT is the textbook one, isn't it?) and use the "fast" algorithm for it to obtain a fast result for the other problem?
Are you thinking of the algorithm that enumerates all possible programs, runs the first for one step, then the first two for two steps each, then the first three for three steps etc, while checking whether any of their outputs satisfy the problem? If P=NP that would solve NP problems in polynomial time, but the constants would probably be universeendingly huge.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
b.i.o wrote:
P is a subset of NP. So for someone to prove that P=NP, they'd have to prove that NP is also a subset of P.
Or you could find a polynomial time algorithm for a problem that is provably in NP.
 SlyReaper
 inflatable
 Posts: 8015
 Joined: Mon Dec 31, 2007 11:09 pm UTC
 Location: Bristol, Old Blighty
Re: P≠NP
BlackSails wrote:b.i.o wrote:
P is a subset of NP. So for someone to prove that P=NP, they'd have to prove that NP is also a subset of P.
Or you could find a polynomial time algorithm for a problem that is provably in NP.
If P is a subset of NP, then all problems solvable in polynomial time are in NP.
What would Baron Harkonnen do?
 b.i.o
 Green is the loneliest number
 Posts: 2519
 Joined: Fri Jul 27, 2007 4:38 pm UTC
 Location: Hong Kong
Re: P≠NP
WarDaft wrote:Aren't there already algorithms for which, if P=NP, could construct the algorithm for any NP problem? That is, they rephrase any NP problem as some particular NP problem that was solved (SAT is the textbook one, isn't it?) and use the "fast" algorithm for it to obtain a fast result for the other problem?
Kind of. What I think you're thinking of is reductions between NPcomplete problems. Typically to show a problem is NPcomplete you have to do two things. The first is to show that it's in NP, which means that a positive answer to the decision problem can be verified in polynomial time. The second thing you have to do (and what I think you're thinking of) is show that the problem is NPhard, meaning that it's at least as hard as other NPcomplete problems. The way you do that is to define a polynomialtime reduction from an alreadyknown NPcomplete problem to your problem, showing that if you can solve your problem, you can solve the NPcomplete problem without very much additional effort, so your problem is at least as hard as the NPcomplete problem.
So yes, *if* we get a polynomialtime algorithm for an NPcomplete algorithm, then yes, we get algorithms for other NPcomplete problems we know about without too much additional work (since we've already come up with them). However, a proof that P=NP doesn't necessarily give us a polynomialtime algorithm for an NPcomplete problem (or a polynomialtime reduction from an NPcomplete problem to a problem in P).
BlackSails wrote:Or you could find a polynomial time algorithm for a problem that is provably in NP.
As SlyReaper said, no. P is a subset of NP, so that holds for all algorithms in P already. I have recently been reminded though that you don't need to provide a generalized reduction from NP to P to prove that P=NP. It suffices to show that one NPcomplete problem is in P. The reason is that if you have one NPcomplete problem you have them all (as per above), and the NPcomplete problems are the hardest problems in NP (so defining a reduction from any nonNPcomplete problem in NP to an NPcomplete problem is not too difficult).
 majikthise
 Posts: 155
 Joined: Sun Jun 10, 2007 2:28 am UTC
 Location: Bristol, UK
Re: P≠NP
[complexity n00b here]
Whilst I understand the general method of proving suchandsuch an NP problem to be NPcomplete (by reduction from an already known NPcomplete problem), there must have been a different method used for the first problem ever shown to be NPcomplete (there being nothing to compare it to). Could anyone possibly link me to some further reading on this?
[/complexity n00b]
Whilst I understand the general method of proving suchandsuch an NP problem to be NPcomplete (by reduction from an already known NPcomplete problem), there must have been a different method used for the first problem ever shown to be NPcomplete (there being nothing to compare it to). Could anyone possibly link me to some further reading on this?
[/complexity n00b]
Is this a wok that you've shoved down my throat, or are you just pleased to see me?
 Jessica
 Jessica, you're a ...
 Posts: 8337
 Joined: Tue Oct 23, 2007 8:57 pm UTC
 Location: Soviet Canuckistan
Re: P≠NP
Well, there are certain NP problems which are provably NP without reduction. Halting problem, for example. sorry my bad. Try traveling salesman.
For more information about complexity (as you could take courses on this...) there's the wikipedia page on NP
For more information about complexity (as you could take courses on this...) there's the wikipedia page on NP
doogly wrote:On a scale of Mr Rogers to Fascism, how mean do you think we're being?
Belial wrote:My goal is to be the best brain infection any of you have ever had.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: P≠NP
The first problem that was proven NPcomplete was the SAT problem, that I briefly explained earlier. The proof is on this WP page, but without a certain amount of background, ie knowing what a Turing machine is in technical language, you'll have some trouble understanding it.
http://en.wikipedia.org/wiki/CookLevin_theorem
http://en.wikipedia.org/wiki/CookLevin_theorem
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Who is online
Users browsing this forum: No registered users and 26 guests