P≠NP
Moderators: Zamfir, Hawknc, Moderators General, Prelates
 majikthise
 Posts: 155
 Joined: Sun Jun 10, 2007 2:28 am UTC
 Location: Bristol, UK
Re: P≠NP
Thanks. I have a basic grounding in some of the concepts due to having taken various mathematical logic and set theory courses, hopefully that's enough!
Is this a wok that you've shoved down my throat, or are you just pleased to see me?
Re: P≠NP
BlackSails wrote:http://scottaaronson.com/blog/?p=456
He might be wrong, but he is basically the god of computational complexity.
And it looks like if he is wrong he's homeless ( or at least out $200,000 ) and jobless ( or at least has to shift his research).
I sort of hope this paper holds up. It's not as game changing as a proof that P = NP would be, but it seems like in math the more we know the more questions we can ask.
 mercuryseven
 Posts: 207
 Joined: Mon Nov 23, 2009 8:36 am UTC
Re: P≠NP
achan1058 wrote:Really, the author should check the list of people he is sending it to. Having it appearing on random websites prematurely is a bad thing, especially if it should get blown down.
Yeah. And actually, why didn't he do it the "usual" way? Upload in ArXiv while awaiting peer review at a maths journal?
 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
mercuryseven wrote:achan1058 wrote:Really, the author should check the list of people he is sending it to. Having it appearing on random websites prematurely is a bad thing, especially if it should get blown down.
Yeah. And actually, why didn't he do it the "usual" way? Upload in ArXiv while awaiting peer review at a maths journal?
That's an option after you're reasonably sure of what you've written. He was at a much more preliminary stage. Frankly, someone has let this guy down by leaking it like this. If there are errors, he might have been able to iron them out by himself, or with researchers he's close to. But now its all over the place with his name on it when its not what he wanted to release.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P≠NP
Jesting, your "bad news" with circuits isn't quite as final as one might think. Solving arbitrary instances of SAT is in NP, but we don't build arbitrary circuits.
In practice, we can build circuits that are easy to reason about, rather than random ones or ones that are hard to reason about. (note that even random ones could be easy to reason about, on average: what makes (many) NP problems hard is that there are pathological cases).
In practice, we can build circuits that are easy to reason about, rather than random ones or ones that are hard to reason about. (note that even random ones could be easy to reason about, on average: what makes (many) NP problems hard is that there are pathological cases).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: P≠NP
And the proof comes crashing down. It seems that the author of the proof failed to distinguish known P variants of SAT (2SAT, XORSAT) from other SAT variants, and can't explain why his proof fails on them, which is never a good sign.
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.

 Posts: 4008
 Joined: Fri Oct 12, 2007 5:37 am UTC
 Location: San Antonio, Tx
 Contact:
Re: P≠NP
joshz wrote:And the proof comes crashing down. It seems that the author of the proof failed to distinguish known P variants of SAT (2SAT, XORSAT) from other SAT variants, and can't explain why his proof fails on them, which is never a good sign.
So is that supposed to be a "yay!" or a "dawwww"?
Re: P≠NP
It's a bad thing. His proof *should* fail on those cases, but the author of the proof can't explain what in his proof causes them too. i.e. he could be "proving" something which is known to be false.
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.

 Posts: 1
 Joined: Thu Apr 01, 2010 8:38 pm UTC
Re: P≠NP
the practical significance of p versus np comes from cryptology though, because if p=np, then that field is bascially finished.
Fortunately, this is not at all the case. Cryptology has existed for a very long time before public key cryptography (the only kind threatened by the answer to the P=NP question) became the norm, and whether or not P=NP it will continue to thrive. Public key cryptography is, in most cases, only used for key exchange, and the algorithms used for the actual encryption of the vast majority of data are symmetric and will be unaffected by the P=NP question (for example, AES).
Furthermore, quantum computing (which is also independent of P=NP) will eventually allow us to factor large numbers extremely efficiently even if P != NP, which will make some very popular algorithms (such as RSA) unsuitable for key exchanges, digital signatures, cryptographic hashes, and/or encryption. It is worth noting that even at that point, the cost and expertise involved in building a quantum computer may still allow these algorithms to be useful for all but the most sensitive of applications for quite some time.
Even that is not the crisis it may seem to be, as there already exists at least one algorithm, I believe from the 1970s, that resists currently known quantum algorithms and may come to replace the popular algorithms in use today.
 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
Yakk wrote:Jesting, your "bad news" with circuits isn't quite as final as one might think. Solving arbitrary instances of SAT is in NP, but we don't build arbitrary circuits.
In practice, we can build circuits that are easy to reason about, rather than random ones or ones that are hard to reason about. (note that even random ones could be easy to reason about, on average: what makes (many) NP problems hard is that there are pathological cases).
That's all true, but if we greatly restrict the possible set of chip designs its reasonable to believe that we disallow the best possible designs.
phormalitize wrote:Even that is not the crisis it may seem to be, as there already exists at least one algorithm, I believe from the 1970s, that resists currently known quantum algorithms and may come to replace the popular algorithms in use today.
I think you're talking about elliptic curve cryptography here? Its probably no worse than RSA, but ultimately, unless you can prove what complexity class your decryption problem resides in, you're really trusting to luck that no one will (or has and isn't telling) crack your method sometime soon. Its a slightly unsettling state of affairs that RSA is known to be subexponential for instance.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: P≠NP
jestingrabbit wrote:Yakk wrote:Jesting, your "bad news" with circuits isn't quite as final as one might think. Solving arbitrary instances of SAT is in NP, but we don't build arbitrary circuits.
In practice, we can build circuits that are easy to reason about, rather than random ones or ones that are hard to reason about. (note that even random ones could be easy to reason about, on average: what makes (many) NP problems hard is that there are pathological cases).
That's all true, but if we greatly restrict the possible set of chip designs its reasonable to believe that we disallow the best possible designs.
Fortunately, when it comes to logic optimization, "good enough" is good enough more times than not. Remarkably, our ability to synthesize and formally verify VLSI devices is gaining on our ability to fabricate them, due in no small measure to techniques like binary decision diagrams which scale sufficiently to make tools such as model checking practical for realworld systems.
jestingrabbit wrote:phormalitize wrote:Even that is not the crisis it may seem to be, as there already exists at least one algorithm, I believe from the 1970s, that resists currently known quantum algorithms and may come to replace the popular algorithms in use today.
I think you're talking about elliptic curve cryptography here?
The McEliece cryptosystem is based on a problem called the hidden subgroup problem, but the point you make below still stands.
jestingrabbit wrote:Its probably no worse than RSA, but ultimately, unless you can prove what complexity class your decryption problem resides in, you're really trusting to luck that no one will (or has and isn't telling) crack your method sometime soon. Its a slightly unsettling state of affairs that RSA is known to be subexponential for instance.
True. As phormalitize points out, the McEliece cryptosystem has been proven resistant only to known decryption techniques ("the approach of strong Fourier sampling on which almost all known exponential speedups by quantum algorithms are based" [from the abstract]).
However, it's worth pointing out that while the new work guarantees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks. It's perfectly possible that somebody will develop a quantum algorithm that will tear it apart as easily as Shor's can with the RSA algorithm. "Our results do not rule out other quantum (or classical) attacks," says Dinh and . . . [the source text is a little garbled here]
. . . more likely scenario for future research is that cryptographers will renew their efforts in one of the several other directions that are looking fruitful, such as latticebased algorithms and multivariate cryptography.
"The age of the universe is 100 billion, if the units are dog years."  Sean Carroll
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P≠NP
phormalitize wrote:the practical significance of p versus np comes from cryptology though, because if p=np, then that field is bascially finished.
Fortunately, this is not at all the case. Cryptology has existed for a very long time before public key cryptography (the only kind threatened by the answer to the P=NP question) became the norm, and whether or not P=NP it will continue to thrive. Public key cryptography is, in most cases, only used for key exchange, and the algorithms used for the actual encryption of the vast majority of data are symmetric and will be unaffected by the P=NP question (for example, AES).
Naw, P=NP makes attacks on many cryptographic systems easier. If your plain text data is sufficiently distinct from random noise, and your decryption/encryption algorithms generates noise when you feed it "bad keys", you just ask the question "is there a key starting with the bits "..." that decodes to something that doesn't look like random noise". That is a NP decision problem (with a failure rate).
Now I'm sure there are ways to defend against this, but AES probably lacks those features.
With key approaching the data size, the above kind of approach would fail to work. By that point, you are using nigh on onetime keys, however.
A fast NPcomplete algorithm is like having Superman on your side  there are problems you still cannot solve, but they are thin on the ground.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
A nonconstructive proof of P=NP would not really impact cryptography at all.
Re: P≠NP
A nonconstructive proof of P=NP would piss off so many people, they wouldn't have time to spend their million dollars. Also, it would lead to the greatest, fastest collaborative effort to find a constructive proof that the world has ever seen.
Re: P≠NP
A nonconstructive proof of P=NP would most likely use the axiom of choice, and then the vast collaborative effort would continue year after year fruitlessly. Meanwhile a confident minority would quietly smile to themselves, knowing the axiom of choice is false in our universe.
wee free kings
Re: P≠NP
Now that would really piss people off. Gödel proved that, under the assumption that ZFM is consistent, ZFM including the axiom of choice is as well. AC being false would (at least as far as I can think this early in the morning) lead to the inconsistency of ZFM  and that really sucks. (Really in the sense of "science is screwed")Qaanol wrote:knowing the axiom of choice is false in our universe.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
jasondx wrote:Now that would really piss people off. Gödel proved that, under the assumption that ZFM is consistent, ZFM including the axiom of choice is as well. AC being false would (at least as far as I can think this early in the morning) lead to the inconsistency of ZFM  and that really sucks. (Really in the sense of "science is screwed")Qaanol wrote:knowing the axiom of choice is false in our universe.
Not really. Physics doesnt care much what math is founded upon.
A nonconstructive proof could also rely on some sort of oracle technique
 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
jasondx wrote:AC being false would (at least as far as I can think this early in the morning) lead to the inconsistency of ZFM
Nah, it wouldn't. There are a bunch of axioms that you can tack onto ZFM that are "as consistent" as ZFM, and as consistent as tacking on their negation. The continuum hypothesis is probably the most famous.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: P≠NP
Its simple: Thanks to Gödel we know that the consitency of ZFM implies the consitency of ZFM+AC. Hence: If ZFM+AC is not consistent, neither is ZFM.jestingrabbit wrote:There are a bunch of axioms that you can tack onto ZFM that are "as consistent" as ZFM, and as consistent as tacking on their negation. The continuum hypothesis is probably the most famous.
Then: if AC is not consistent, neither is ZFM+AC. (Adding Axioms cannot remove inconsistency). Hence the Inconsitency of AC implies inconsitency of ZFM+AC which implies inconsistency of ZFM.
The Continuum Hypothesis is another story  it is proven to be not provable in a consistent system (Some sort of: The statement is provable if and only if it is false...)
I agree that science in general can be questioned in the statement (It depends what you consider science and what not ). But physics rely a lot on math, hence depend on its soundness.BlackSails wrote:jasondx wrote:Now that would really piss people off. Gödel proved that, under the assumption that ZFM is consistent, ZFM including the axiom of choice is as well. AC being false would (at least as far as I can think this early in the morning) lead to the inconsistency of ZFM  and that really sucks. (Really in the sense of "science is screwed")Qaanol wrote:knowing the axiom of choice is false in our universe.
Not really. Physics doesnt care much what math is founded upon.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: P≠NP
I agree that science in general can be questioned in the statement (It depends what you consider science and what not ). But physics rely a lot on math, hence depend on its soundness.[/quote]jasondx wrote:Not really. Physics doesnt care much what math is founded upon.
Why does physics care what math can and cant say about transfinite sets and such?
Re: P≠NP
Because if ZFM is inconsistent, so is PE, and many other systems. With PE it should be more obvious why it is relevant for physics. And the problem in this case (that AC is false) would not be that math cannot prove certain statements  its that you can prove everything, including contradicting statements.BlackSails wrote:Why does physics care what math can and cant say about transfinite sets and such?
 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
jasondx wrote:Its simple: Thanks to Gödel we know that the consitency of ZFM implies the consitency of ZFM+AC. Hence: If ZFM+AC is not consistent, neither is ZFM.jestingrabbit wrote:There are a bunch of axioms that you can tack onto ZFM that are "as consistent" as ZFM, and as consistent as tacking on their negation. The continuum hypothesis is probably the most famous.
Then: if AC is not consistent, neither is ZFM+AC. (Adding Axioms cannot remove inconsistency). Hence the Inconsitency of AC implies inconsitency of ZFM+AC which implies inconsistency of ZFM.
The Continuum Hypothesis is another story  it is proven to be not provable in a consistent system (Some sort of: The statement is provable if and only if it is false...)
You seem to be conflating "consistent" and "true". Qaanol said that AC was false. That doesn't mean that ZF+AC is inconsistent, its just false in our universe.
And CH is just independent of ZF+AC, like AC is independent of ZF.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: P≠NP
I cannot really genuinely disagree, only try to disprove you (or me ). According to my interpretations, sentences (in a system) can be either true or false. A system then is consistent, if only true sentences can be proven, and is inconsistent otherwise. If a sentence is independend from a system, that means that it cannot be proven or disproven using (only) the systems axioms. Such sentences only exist in incomplete systems. This is my basic understanding for the terms in this topic, did I misunderstand some parts?jestingrabbit wrote:You seem to be conflating "consistent" and "true".
Which means that ZF+AC includes an axiom that is false.jestingrabbit wrote:Qaanol said that AC was false.
I don't really understand that: If an axiom of a system is false, how can that system be consistent?jestingrabbit wrote:That doesn't mean that ZF+AC is inconsistent, its just false in our universe.
Re: P≠NP
jasondx wrote:I don't really understand that: If an axiom of a system is false, how can that system be consistent?
Because axioms are just things we take as true. We don't need to prove them. It's possible to make a system with one axiom and have it be consistent but also to make a system with in place of that axiom have the complete opposite and it still be consistent (depending on the axiom).
Euclidean geometry has a set of axioms and those specify a consistent system. However, when we try to apply that euclidean geometry to certain things we realize that they follow a different geometry. The axioms in euclidean geometry created a consistent system but it ended up that at least one of the axioms for euclidean geometry doesn't hold for all the things we want to apply it on.
double epsilon = .0000001;
Re: P≠NP
Err... I think people are bandying the word 'false' around improperly.
The issue of consistency vs. 'truth' comes down to what we think our Model of set theory looks like. The reason why we care about the axioms of set theory is that mathematicians have some idea of how sets are supposed to work. That is, ideally, mathematicians should have some model of set theory in mind, and the axioms are intended to be an axiomatization of the Theory of that Model (i.e., they are an attempt to axiomatize all true statements you can make about that model). There are a number of problems with this: The first is that we don't have a precise knowledge of how sets are supposed to behave, and its kind of an illdefined concept to begin with. Secondly, even if we did, trying to give an axiomatization of its theory is going to inevitably fail (see Godel).
Anyways, if we knew that some set of axioms were inconsistent, then there can be no model satisfying those axioms, so in particular we know that (at the very least) they don't capture our nebulously defined model of what set theory should look like. Thus, if we knew that either ZF+AC or ZF + not AC were inconsistent, we could throw it out. However, we believe both of them to be consistent, in which case both are likely to actually have real models (can't remember if they necessarily do: can we apply 'consistency implies satisfiability' here).
Thus, what we mean by 'AC is false in our universe' is that in our nebulously defined model of set theory, the axiom of choice does not hold. This doesn't preclude the existence of other models of set theory in which it does hold, just that we don't think of such a model as describing what 'being a set' 'means'.
TL;DR: Try not to claim that 'AC is false in our universe' as that's confusing. Better to say that 'AC doesn't describe sets as we understand sets to work'.
Also: models of set theory will destroy your brain. What's a model? It's a set with some elements and predicates that has some true statements about it. Did I use the word 'set'? In describing models of 'set theory'? Oh damn, guess we're boned.
The issue of consistency vs. 'truth' comes down to what we think our Model of set theory looks like. The reason why we care about the axioms of set theory is that mathematicians have some idea of how sets are supposed to work. That is, ideally, mathematicians should have some model of set theory in mind, and the axioms are intended to be an axiomatization of the Theory of that Model (i.e., they are an attempt to axiomatize all true statements you can make about that model). There are a number of problems with this: The first is that we don't have a precise knowledge of how sets are supposed to behave, and its kind of an illdefined concept to begin with. Secondly, even if we did, trying to give an axiomatization of its theory is going to inevitably fail (see Godel).
Anyways, if we knew that some set of axioms were inconsistent, then there can be no model satisfying those axioms, so in particular we know that (at the very least) they don't capture our nebulously defined model of what set theory should look like. Thus, if we knew that either ZF+AC or ZF + not AC were inconsistent, we could throw it out. However, we believe both of them to be consistent, in which case both are likely to actually have real models (can't remember if they necessarily do: can we apply 'consistency implies satisfiability' here).
Thus, what we mean by 'AC is false in our universe' is that in our nebulously defined model of set theory, the axiom of choice does not hold. This doesn't preclude the existence of other models of set theory in which it does hold, just that we don't think of such a model as describing what 'being a set' 'means'.
TL;DR: Try not to claim that 'AC is false in our universe' as that's confusing. Better to say that 'AC doesn't describe sets as we understand sets to work'.
Also: models of set theory will destroy your brain. What's a model? It's a set with some elements and predicates that has some true statements about it. Did I use the word 'set'? In describing models of 'set theory'? Oh damn, guess we're boned.
 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
Anyway, this is all irrelevant. There are (incredibly inefficient) algorithms that do NPcomplete problems in polynomial time if P=NP.
http://en.wikipedia.org/wiki/P_versus_N ... algorithms
So basically, a non constructive proof wouldn't actually be a problem that could come down to which axioms are or aren't true in this universe or however you want to put it.
And anyway, as PM 2ring or yakk pointed out earlier, there are pretty good algorithms already out there.
http://en.wikipedia.org/wiki/P_versus_N ... algorithms
So basically, a non constructive proof wouldn't actually be a problem that could come down to which axioms are or aren't true in this universe or however you want to put it.
And anyway, as PM 2ring or yakk pointed out earlier, there are pretty good algorithms already out there.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P≠NP
jestingrabbit wrote:Anyway, this is all irrelevant. There are (incredibly inefficient) algorithms that do NPcomplete problems in polynomial time if P=NP.
There could be a "what exactly do you mean by 'finite'" problem. Ie, we find that with the AoC and the standard axioms of computer science, there is an essentially nonconstructive proof that there must be an algorithm that runs in P time that solves a NP complete problem.
Ie, the AoC, while equiconsistent with ZF(M), ends up being the equivalent of taking a godel axiom that adds new elements to the set of algorithms that are "optional".
The countability of algorithms makes me think this is unlikely, but I don't know enough hardcore model theory to discount the possibility personally.
http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomialtime_algorithms
So basically, a non constructive proof wouldn't actually be a problem that could come down to which axioms are or aren't true in this universe or however you want to put it.
And anyway, as PM 2ring or yakk pointed out earlier, there are pretty good algorithms already out there.
Ie, the above "eventually" produces the algorithm in question, but it takes a finite period of time that is actually nonfinite (as in, a nonstandard number of steps).
In that case, one could see that it would be interpreted as "the AoC is nottrue in our universe".
Do you know if the countable sets in ZF(M)+C are the same as the countable sets in ZF(M)+~C? (I don't know how to say that nicely, because my model theory sucks  I don't even know if there is a decent way to say it...)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 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
Yakk wrote:Do you know if the countable sets in ZF(M)+C are the same as the countable sets in ZF(M)+~C? (I don't know how to say that nicely, because my model theory sucks  I don't even know if there is a decent way to say it...)
You need choice to prove that a countable union of countable sets is countable, so I'd think that you do get different collections of countable sets.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P≠NP
*nod*, now I remember: my friend liked an axiom of countable choice for that reason.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Who is online
Users browsing this forum: No registered users and 13 guests