Guest Speakers: Harvey Friedman
Part of the RESOLVE-2018 Workshop
Dreese Labs 480
2015 Neil Ave, Columbus, Ohio 43210
This Foundationalist Looks at P = NP
Conventional Wisdom tells us that the possibility that the presently intractable theoretical computer science problems such as P = NP are so difficult because they are neither provable nor refutable in the usual ZFC axioms for mathematics, is too far fetched to deserve any serious consideration.
Until recently, we completely agreed with this CW. However, there have been some major advances in discrete and even purely finitary examples of independence from ZFC that are now sufficiently basic and transparent that we believe that the possibility of P = NP and related problems being independent of ZFC is at least worthy of consideration.
We will discuss these new natural examples, and present one of them, Maximal Emulation Stability, particularly slowly and carefully, in order to engage and hopefully interact with an audience of computer scientists and other scholars. In addition, an older example of ours is being championed by Gill Williamson as a possible vehicle for establishing the independence of P = NP from ZFC.