[FOM] Finite functions and necessary use of large cardinals

[Joe Shipman]

This is quite striking. Harvey can probably shed light on whether the subclass of graph theorems that you can derive from P=NP as well as from subtle cardinals is sufficiently broad that his “reversals” can be adapted to them. If so, then you will have shown that P=NP is independent and P!=NP is consistent.  

If not, i.e. if the subclass of graph theorems is narrow enough to be provable in ZFC,  then this may shed light on the subset sum problem, although it seems unlikely that the relevant easy instances of subset sum will threaten to entail P=NP (because we already know that subset sum is not very strongly NP-complete, being PTIME approximable and pseudo-Ptime solvable).

— JS

Sent from my iPhone

> On Nov 12, 2019, at 11:36 AM, S. Gill Williamson <gill.williamson at gmail.com> 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:
> 
> -- Gill Williamson
> 
> https://arxiv.org/abs/1907.11707v2
> _______________________________________________
> 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/20191112/f651993d/attachment.html>