[FOM] Finite functions and necessary use of large cardinals

[martdowd at aol.com]

FOM
I have not had time to read the paper yet, but a question occurs to me.  Why is polynomial time of any significance?For example, is there an analogous result for detemiistic exponential time?
Martin Dowd
 
 
 
-----Original Message-----
From: S. Gill Williamson <gill.williamson at gmail.com>
To: tchow <tchow at alum.mit.edu>; Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Wed, Nov 13, 2019 11:09 pm
Subject: Re: [FOM] Finite functions and necessary use of large cardinals

Hi Tim,
Your concerns are certainly relevant.  Referring to the arXiv paper reference I sent you:
I have had plenty of feedback on this paper (referees for the JOC version [Wil17c], logician friends).  We think the proofs as stated are correct.   A key paper not published is [Fri97].  I went over this paper with Jeff in 1999.  Recently, Victor Marek has gone over some of the key results, like the Jump Free Theorem, with Harvey. 
The remark on page 10 of my arXiv  paper  (“Remark: Independence of the families of Theorem 5.4”)  is important relative to your comments.  This refers to [Fri97].  Harvey seems to be going back to this area in his new FOM program.  I hope so.
If Theorem 6.7 turns out to be provable in ZFC, it would be a nice addition to combinatorics.   On the other hand if Theorem 6.7 is shown to be unprovable in ZFC that would be interesting also.  It would support the common belief that P=NP is false.
My hope for this paper is that turns out to be "fun and interesting to think about" for people interested in logic, algorithms and complexity theory.
-- Gill
On Tue, Nov 12, 2019 at 4:38 PM Timothy Y. Chow <tchow at math.princeton.edu> wrote:

Gill Williamson wrote:

> Below is a link to my latest thoughts on connections between Harvey
> Friedman's 1998 paper (Annals of Mathematics) and the P vs NP problem:
> 
> https://arxiv.org/abs/1907.11707v2

This is an intriguing suggestion, but I thought that one lesson from 
Friedman's Boolean relation theory was that a seemingly innocuous "tweak" 
of statement to a superficially similar statement can abruptly switch it 
from unprovable in ZFC to trivially provable in an extremely weak system. 
So it seems very bold to me to conjecture that a whole family of 
superficially similar statements are all unprovable in ZFC just because 
some, or even most, of them are.

Tim
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
https://cs.nyu.edu/mailman/listinfo/fom

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
https://cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20191114/bf01a2bd/attachment.html>