On the consistency of P \neq NP with ZFC
Gill Williamson (UCSD)
Monday, June 2nd 2025, 2-3pm
Abstract:
Our main result, Theorem 3.3, uses Friedman’s Jump Free Theorem, Theorem 2.7, which he has shown to be independent of ZFC, the usual axioms of set theory [Fri97]. We conjecture that Theorem 3.3, a straight forward translation of the statement of Theorem 2.7 into sets and functions, is also independent of ZFC as is its immediate Corollary 3.4. It is easy to show that a proof that P=NP will prove Corollary 3.4. If Corollary 3.4 is in fact independent of ZFC then a ZFC proof of P=NP is impossible and, in fact, P=NP is itself independent of ZFC (or perhaps false).