P≠NP

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

Moderators: Zamfir, Hawknc, Moderators General, Prelates

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 5:07 pm UTC

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?

User avatar
DorkRawk
Posts: 51
Joined: Thu Mar 08, 2007 6:50 am UTC
Location: Chicago
Contact:

Re: P≠NP

Postby DorkRawk » Tue Aug 10, 2010 5:46 pm UTC

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.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: P≠NP

Postby achan1058 » Wed Aug 11, 2010 12:45 am UTC

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.

User avatar
mercuryseven
Posts: 207
Joined: Mon Nov 23, 2009 8:36 am UTC

Re: P≠NP

Postby mercuryseven » Wed Aug 11, 2010 5:19 am UTC

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?

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 » Wed Aug 11, 2010 11:57 am UTC

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.

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

Postby Yakk » Tue Aug 17, 2010 3:13 pm UTC

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

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

Re: P≠NP

Postby joshz » Tue Aug 17, 2010 3:28 pm UTC

And the proof comes crashing down. It seems that the author of the proof failed to distinguish known P variants of SAT (2-SAT, XOR-SAT) 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.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

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 17, 2010 5:27 pm UTC

joshz wrote:And the proof comes crashing down. It seems that the author of the proof failed to distinguish known P variants of SAT (2-SAT, XOR-SAT) 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"?

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

Re: P≠NP

Postby joshz » Tue Aug 17, 2010 5:31 pm UTC

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

phormalitize
Posts: 1
Joined: Thu Apr 01, 2010 8:38 pm UTC

Re: P≠NP

Postby phormalitize » Fri Aug 20, 2010 12:56 pm UTC

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.

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 » Fri Aug 20, 2010 2:41 pm UTC

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.

User avatar
ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

Re: P≠NP

Postby ATCG » Fri Aug 20, 2010 4:33 pm UTC

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 real-world 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 lattice-based algorithms and multivariate cryptography.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

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

Postby Yakk » Mon Aug 23, 2010 1:15 am UTC

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 one-time keys, however.

A fast NP-complete 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.

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

Re: P≠NP

Postby BlackSails » Mon Aug 23, 2010 3:00 am UTC

A nonconstructive proof of P=NP would not really impact cryptography at all.

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: P≠NP

Postby letterX » Mon Aug 23, 2010 6:37 am UTC

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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: P≠NP

Postby Qaanol » Mon Aug 23, 2010 7:37 am UTC

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

jasondx
Posts: 4
Joined: Fri Jul 09, 2010 5:58 am UTC

Re: P≠NP

Postby jasondx » Mon Aug 23, 2010 8:58 am UTC

Qaanol wrote:knowing the axiom of choice is false in our universe.
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")

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

Re: P≠NP

Postby BlackSails » Mon Aug 23, 2010 12:10 pm UTC

jasondx wrote:
Qaanol wrote:knowing the axiom of choice is false in our universe.
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")


Not really. Physics doesnt care much what math is founded upon.


A nonconstructive proof could also rely on some sort of oracle technique

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 23, 2010 12:11 pm UTC

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.

jasondx
Posts: 4
Joined: Fri Jul 09, 2010 5:58 am UTC

Re: P≠NP

Postby jasondx » Mon Aug 23, 2010 10:06 pm UTC

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


BlackSails wrote:
jasondx wrote:
Qaanol wrote:knowing the axiom of choice is false in our universe.
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")


Not really. Physics doesnt care much what math is founded upon.
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.

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

Re: P≠NP

Postby BlackSails » Mon Aug 23, 2010 10:54 pm UTC

jasondx wrote:Not really. Physics doesnt care much what math is founded upon.
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]

Why does physics care what math can and cant say about transfinite sets and such?

jasondx
Posts: 4
Joined: Fri Jul 09, 2010 5:58 am UTC

Re: P≠NP

Postby jasondx » Tue Aug 24, 2010 6:37 am UTC

BlackSails wrote:Why does physics care what math can and cant say about transfinite sets and such?
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.

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 24, 2010 7:47 am UTC

jasondx wrote:
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.
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.
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.

jasondx
Posts: 4
Joined: Fri Jul 09, 2010 5:58 am UTC

Re: P≠NP

Postby jasondx » Tue Aug 24, 2010 1:37 pm UTC

jestingrabbit wrote:You seem to be conflating "consistent" and "true".
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:Qaanol said that AC was false.
Which means that ZF+AC includes an axiom that is false.
jestingrabbit wrote:That doesn't mean that ZF+AC is inconsistent, its just false in our universe.
I don't really understand that: If an axiom of a system is false, how can that system be consistent?

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: P≠NP

Postby Dason » Tue Aug 24, 2010 4:02 pm UTC

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;

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: P≠NP

Postby letterX » Tue Aug 24, 2010 4:37 pm UTC

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

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 24, 2010 5:21 pm UTC

Anyway, this is all irrelevant. There are (incredibly inefficient) algorithms that do NP-complete 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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Postby Yakk » Tue Aug 24, 2010 5:43 pm UTC

jestingrabbit wrote:Anyway, this is all irrelevant. There are (incredibly inefficient) algorithms that do NP-complete 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 non-constructive 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 hard-core model theory to discount the possibility personally.

http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_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 non-finite (as in, a non-standard number of steps).

In that case, one could see that it would be interpreted as "the AoC is not-true 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.

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 24, 2010 5:56 pm UTC

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.

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

Postby Yakk » Tue Aug 24, 2010 7:17 pm UTC

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


Return to “News & Articles”

Who is online

Users browsing this forum: No registered users and 13 guests