[FOM] "Mere" correctness of a proof

[Miguel A. Lerma]

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)