Complexity of proofs

Timothy Y. Chow tchow at
Sat Jul 25 14:06:00 EDT 2020

Andrew Winkler wrote:
> I recall hearing of a theorem that said something along the lines of 
> generic axioms give rise to theorems whose proofs are exponential in the 
> lengths of their statements. It's not clear to me how to make that 
> precise. Has anyone heard this? Any pointers you could give me for 
> tracking it down? Thanks!

Well, there's this old trick:

G: "There is no proof of G with fewer than 10^100 symbols."

Is that good enough for your purposes?


More information about the FOM mailing list