Timeline for Independence of P = NP?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2010 at 13:34 | comment | added | David E Speyer | We discussed this issue over at math.SE, maybe reading math.stackexchange.com/questions/5377 would help you. | |
| Dec 21, 2010 at 10:39 | history | edited | Jason | CC BY-SA 2.5 |
Additions to address comments
|
| Dec 21, 2010 at 5:36 | comment | added | Jason | Let me restate what I'm saying because you're right, the logic would be circular with this assumption. If PA is not consistent, then every statement is provable in PA. This is because everything follows from a contradiction. So if this were the case, then we'd have a proof of both CON(PA) and ~CON(PA). And I guess technically then CON(PA) would not be independent of ZFC, but then we'd also have a proof of both P = NP and P $\neq$ NP and no set-theoretic universe. | |
| Dec 21, 2010 at 5:18 | comment | added | Zirui Wang | Godel's second incompleteness theorem assumes Con(PA). It states: If Con(PA), then Con(PA) is not provable. | |
| Dec 21, 2010 at 5:11 | comment | added | Jason | If Con(PA) is not provable from PA, then PA is consistent because if a theory is inconsistent, then every statement is provable from that theory. | |
| Dec 21, 2010 at 5:08 | comment | added | Zirui Wang | Who says Con(PA) is independent of PA? Godel's second incompleteness theorem only asserts Con(PA) is not provable. ~Con(PA) might be provable in PA. | |
| Dec 21, 2010 at 4:49 | history | answered | Jason | CC BY-SA 2.5 |