P≠NP

Seen something interesting in the news or on the intertubes? Discuss it here.

Moderators: Zamfir, Hawknc, Moderators General, Prelates

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

P≠NP

Postby joshz » Mon Aug 09, 2010 1:50 am UTC

A researcher's published a paper claiming to prove that P≠NP. It hasn't been peer-reviewed yet, but it looks promising.
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.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
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.

Re: P≠NP

Postby TheGrammarBolshevik » Mon Aug 09, 2010 1:59 am UTC

Here's some background from reddit showing that, whether it turns out to work or not, it's a serious attempt by an established computer scientist. Not a crank.
Nothing rhymes with orange,
Not even sporange.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Mon Aug 09, 2010 2:12 am UTC

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.

Outchanter
Posts: 669
Joined: Mon Dec 17, 2007 8:40 am UTC

Re: P≠NP

Postby Outchanter » Mon Aug 09, 2010 2:24 am UTC

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

User avatar
CorruptUser
Posts: 10550
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: P≠NP

Postby CorruptUser » Mon Aug 09, 2010 5:02 am UTC

If true, [angry_sobbing]why?[/angry_sobbing]

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Mon Aug 09, 2010 5:15 am UTC

CorruptUser wrote:If true, [angry_sobbing]why?[/angry_sobbing]


It would be very terrible if P were to equal NP.

User avatar
CorruptUser
Posts: 10550
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: P≠NP

Postby CorruptUser » Mon Aug 09, 2010 5:22 am UTC

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?

PeterCai
Posts: 865
Joined: Tue Feb 17, 2009 1:09 pm UTC

Re: P≠NP

Postby PeterCai » Mon Aug 09, 2010 5:27 am UTC

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.

bosonicyouth
Posts: 92
Joined: Sat May 01, 2010 8:59 am UTC
Location: Brisbane, Australia

Re: P≠NP

Postby bosonicyouth » Mon Aug 09, 2010 5:32 am UTC

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

User avatar
CorruptUser
Posts: 10550
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: P≠NP

Postby CorruptUser » Mon Aug 09, 2010 5:34 am UTC

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.
Last edited by CorruptUser on Mon Aug 09, 2010 5:38 am UTC, edited 4 times in total.

User avatar
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.

Re: P≠NP

Postby TheGrammarBolshevik » Mon Aug 09, 2010 5:35 am UTC

Nothing rhymes with orange,
Not even sporange.

User avatar
netcrusher88
Posts: 2166
Joined: Mon Mar 26, 2007 4:35 pm UTC
Location: Seattle

Re: P≠NP

Postby netcrusher88 » Mon Aug 09, 2010 5:40 am UTC

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 WPA-PSK works is computationally expensive and salted with the ESSID or something) you can pre-generate 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 non-dictionary password before you hash it (and use non-dictionary 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

User avatar
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

Postby jestingrabbit » Mon Aug 09, 2010 6:11 am UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Outchanter
Posts: 669
Joined: Mon Dec 17, 2007 8:40 am UTC

Re: P≠NP

Postby Outchanter » Mon Aug 09, 2010 6:48 am UTC

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 NP-complete problems, even though they're all technically equivalent. I think it was also the first one to be proven NP-complete, 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>.

Minchandre
Posts: 524
Joined: Thu Nov 08, 2007 3:36 am UTC

Re: P≠NP

Postby Minchandre » Mon Aug 09, 2010 10:14 am UTC

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.

User avatar
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

Postby fjafjan » Mon Aug 09, 2010 12:07 pm UTC

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?
//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.

User avatar
Goldstein
Posts: 985
Joined: Wed Nov 05, 2008 9:38 pm UTC
Location: Newcastle, UK

Re: P≠NP

Postby Goldstein » Mon Aug 09, 2010 2:08 pm UTC

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

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Mon Aug 09, 2010 2:29 pm UTC

http://scottaaronson.com/blog/?p=456

He might be wrong, but he is basically the god of computational complexity.

User avatar
Godskalken
Posts: 159
Joined: Wed May 14, 2008 3:29 pm UTC

Re: P≠NP

Postby Godskalken » Mon Aug 09, 2010 3:51 pm UTC

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.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Mon Aug 09, 2010 4:15 pm UTC

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.

User avatar
Godskalken
Posts: 159
Joined: Wed May 14, 2008 3:29 pm UTC

Re: P≠NP

Postby Godskalken » Mon Aug 09, 2010 4:55 pm UTC

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.

User avatar
Jessica
Jessica, you're a ...
Posts: 8337
Joined: Tue Oct 23, 2007 8:57 pm UTC
Location: Soviet Canuckistan

Re: P≠NP

Postby Jessica » Mon Aug 09, 2010 5:12 pm UTC

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.

PeterCai
Posts: 865
Joined: Tue Feb 17, 2009 1:09 pm UTC

Re: P≠NP

Postby PeterCai » Mon Aug 09, 2010 5:15 pm UTC

so how exactly would a p=/=np proof affect us? isn't that the assumed answer?

User avatar
Jessica
Jessica, you're a ...
Posts: 8337
Joined: Tue Oct 23, 2007 8:57 pm UTC
Location: Soviet Canuckistan

Re: P≠NP

Postby Jessica » Mon Aug 09, 2010 5:16 pm UTC

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.

User avatar
joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

Re: P≠NP

Postby joshz » Mon Aug 09, 2010 5:32 pm UTC

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.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

User avatar
Jesse
Vocal Terrorist
Posts: 8635
Joined: Mon Jul 03, 2006 6:33 pm UTC
Location: Basingstoke, England.
Contact:

Re: P≠NP

Postby Jesse » Mon Aug 09, 2010 6:04 pm UTC

It would turn an assumption into a fact.

User avatar
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

Postby jestingrabbit » Mon Aug 09, 2010 6:41 pm UTC

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.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Mon Aug 09, 2010 7:32 pm UTC

I believe there are several other seperations of complexity classes that are only true if P=NP (or if P!=NP)

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: P≠NP

Postby ++$_ » Mon Aug 09, 2010 7:35 pm UTC

BlackSails wrote:http://scottaaronson.com/blog/?p=456

He might be wrong, but he is basically the god of computational complexity.
It sounds like he doesn't think the proof is right, which is always a good bet.

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.

Osha
Posts: 727
Joined: Wed Dec 03, 2008 3:24 am UTC
Location: Boise, Idaho, USA

Re: P≠NP

Postby Osha » Tue Aug 10, 2010 1:27 am UTC

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.

The Reaper
Posts: 4008
Joined: Fri Oct 12, 2007 5:37 am UTC
Location: San Antonio, Tx
Contact:

Re: P≠NP

Postby The Reaper » Tue Aug 10, 2010 2:41 am UTC

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!

User avatar
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

Postby b.i.o » Tue Aug 10, 2010 5:11 am UTC

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 polynomial-time 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 free--it 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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: P≠NP

Postby WarDaft » Tue Aug 10, 2010 5:16 am UTC

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.

Outchanter
Posts: 669
Joined: Mon Dec 17, 2007 8:40 am UTC

Re: P≠NP

Postby Outchanter » Tue Aug 10, 2010 7:01 am UTC

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 universe-endingly huge.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: P≠NP

Postby BlackSails » Tue Aug 10, 2010 11:13 am UTC

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.

User avatar
SlyReaper
inflatable
Posts: 8015
Joined: Mon Dec 31, 2007 11:09 pm UTC
Location: Bristol, Old Blighty

Re: P≠NP

Postby SlyReaper » Tue Aug 10, 2010 11:29 am UTC

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.
Image
What would Baron Harkonnen do?

User avatar
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

Postby b.i.o » Tue Aug 10, 2010 1:56 pm UTC

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 NP-complete problems. Typically to show a problem is NP-complete 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 NP-hard, meaning that it's at least as hard as other NP-complete problems. The way you do that is to define a polynomial-time reduction from an already-known NP-complete problem to your problem, showing that if you can solve your problem, you can solve the NP-complete problem without very much additional effort, so your problem is at least as hard as the NP-complete problem.

So yes, *if* we get a polynomial-time algorithm for an NP-complete algorithm, then yes, we get algorithms for other NP-complete 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 polynomial-time algorithm for an NP-complete problem (or a polynomial-time reduction from an NP-complete 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 NP-complete problem is in P. The reason is that if you have one NP-complete problem you have them all (as per above), and the NP-complete problems are the hardest problems in NP (so defining a reduction from any non-NP-complete problem in NP to an NP-complete problem is not too difficult).

User avatar
majikthise
Posts: 155
Joined: Sun Jun 10, 2007 2:28 am UTC
Location: Bristol, UK

Re: P≠NP

Postby majikthise » Tue Aug 10, 2010 2:30 pm UTC

[complexity n00b here]
Whilst I understand the general method of proving such-and-such an NP problem to be NP-complete (by reduction from an already known NP-complete problem), there must have been a different method used for the first problem ever shown to be NP-complete (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?

User avatar
Jessica
Jessica, you're a ...
Posts: 8337
Joined: Tue Oct 23, 2007 8:57 pm UTC
Location: Soviet Canuckistan

Re: P≠NP

Postby Jessica » Tue Aug 10, 2010 3:27 pm UTC

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

User avatar
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

Postby jestingrabbit » Tue Aug 10, 2010 4:54 pm UTC

The first problem that was proven NP-complete 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/Cook-Levin_theorem
ameretrifle wrote:Magic space feudalism is therefore a viable idea.


Return to “News & Articles”

Who is online

Users browsing this forum: No registered users and 15 guests