Timeline for Are there any natural theories T for which P=NP implies T proves P=NP?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 28, 2017 at 0:01 | comment | added | Dan Brumleve | I think this is basically asking whether $\text{P} \neq \text{NP}$ is equivalent to any $\Pi_1$ sentence. This is non-trivially the case with RH for example, so if RH is false then PA proves that. There is an article about this subject on Dick Lipton's blog that you may be interested in. | |
| Jan 2, 2017 at 3:38 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 3, 2016 at 16:24 | comment | added | Andrew Polonsky | Let us continue this discussion in chat. | |
| Dec 3, 2016 at 16:21 | comment | added | John Bentin | I think I'm beginning to understand you now: If ¬GC holds, then simply checking GC/¬GC for the individual cases 4, 6, etc.---a purely PA process---will eventually terminate and so constitute a proof of ¬GC purely within PA. The rules of your "$A$ implies" seem to be that we may posit $A$ to draw from it information about what kind of proofs are possible within $T$, but no reference to $A$ as an assumable statement may be made within any $T$-based proof. Please explain if this interpretation is unclear, imprecise, or wrong. | |
| Dec 3, 2016 at 14:39 | comment | added | Andrew Polonsky | Also false. If A is the negation of Goldbach's conjecture, then PA proves A, "without including any assumption beyond PA" in the proof. | |
| Dec 3, 2016 at 10:54 | comment | added | John Bentin | Of course, PA does not prove Con(PA) if we can include no assumption beyond PA in any proof. But this stricture entails that the "$A$ implies" (i.e. Con(PA) implies) part of the statement is without any force and is effectively redundant. So, returning to the original question, what exactly do you mean by "P=NP implies"? | |
| Dec 3, 2016 at 2:20 | answer | added | none | timeline score: -1 | |
| Dec 2, 2016 at 23:47 | comment | added | Andrew Polonsky | Counterexample.T=PA. A=Con(PA). | |
| Dec 2, 2016 at 22:53 | comment | added | John Bentin | By elementary logic, if we premise a proposition $A$ (e.g. P=NP), then any theory whatsoever, including (say) ZFC + $\lnot A$, can prove $A$: Just write down any true statements of the theory you like (or none, if you prefer); then introduce $A$; and $A$ follows immediately. | |
| Dec 2, 2016 at 21:05 | comment | added | Andrew Polonsky | I mean the former. If you have the answer, please share it. Even (and especially!) if it seems trivial. ;) | |
| Dec 2, 2016 at 14:56 | comment | added | John Bentin | Trivially, "P=NP implies T proves P=NP" holds if we parse it as P=NP implies (T proves P=NP). So I guess that you mean (P=NP implies T) proves P=NP. | |
| Dec 2, 2016 at 7:09 | history | edited | Andrew Polonsky | CC BY-SA 3.0 |
improved phrasing
|
| Dec 1, 2016 at 23:17 | review | First posts | |||
| Dec 2, 2016 at 0:20 | |||||
| Dec 1, 2016 at 23:07 | history | asked | Andrew Polonsky | CC BY-SA 3.0 |