[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