Timeline for complexity of proof of p(n) grows greater with n if for all x P(x) is unprovable?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2014 at 15:51 | comment | added | Emil Jeřábek | See users.math.cas.cz/~pudlak/fin-con.pdf . | |
| Sep 29, 2014 at 15:00 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
deleted 336 characters in body
|
| Sep 29, 2014 at 14:40 | comment | added | Joel David Hamkins | Yes, I think that is right, since $n$ codes a sequence about length $\log n$. It seems to me, further, that one can push this much slower even, by modifying $P(n)$ to require a bunch of irrelevant padding, so that the extra checking is not required beyond something much further less than $n$. | |
| Sep 29, 2014 at 14:33 | comment | added | David E Speyer | It looks to me like the first example shows that the length of proofs of $P(n)$ can grow quite slowly (something like polynomial in $\log n$, I think) even while $\forall x : P(x)$ is independent. That's something I didn't know, so I appreciate your answer for this reason. | |
| Sep 29, 2014 at 14:32 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 336 characters in body
|
| Sep 29, 2014 at 13:54 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 2 characters in body
|
| Sep 29, 2014 at 13:29 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 18 characters in body
|
| Sep 29, 2014 at 13:18 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |