On P=NP Either False or Independent of ZFC

2024/03/30 by S. Gill Williamson, Williamson, S Gill
Computer Science · #0368 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.2404.00468

openalex publication_date 2024/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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. 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 also prove Corollary 3.4. If Corollary 3.4 is in fact independent of ZFC then a ZFC proof of P=NP is impossible, perhaps because it is false.

Related

• On the difficulty of proving P equals NP in ZFC
• On the consistency of P=NP with fragments of ZFC whose own consistency strength can be measured by an ordinal assignment
• What is the theory ZFC without power set?
• Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP
• Notes on the equiconsistency of ZFC without the Power Set axiom and second order PA