[FOM] "Mere" correctness of a proof
Miguel A. Lerma
mlerma at math.northwestern.edu
Fri Sep 7 12:13:45 EDT 2018
On Fri, Sep 7, 2018 at 1:28 AM Timothy Y. Chow <tchow at math.princeton.edu> wrote:
[...]
> Another possible arena is computational complexity. As longtime FOM
> participants know, I am fond of citing the theorem "Checkers is a draw."
> It is hard to imagine an "explanatory proof" of this theorem that does not
> involve brute-force calculation. Assuming that there is some upper bound
> on how long a proof can be before it ceases to be "explanatory," any
> EXPTIME-complete problem furnishes a family of short theorems which cannot
> all have short proofs.
That reminds me of Wilf's paper:
H. S. Wilf, What is an answer?, Amer. Math. Monthly 89 (1982), 289–292.
The author focuses in counting problems that can be answered with a formula whose computational complexity is less than using brute force.
--
Miguel A. Lerma
Department of Mathematics <mlerma at math.northwestern.edu>
Northwestern University
2033 Sheridan Road 847-491-8020 (w)
Evanston, IL 60208-2730 847-491-8906 (f)
More information about the FOM
mailing list