S. Gill Williamson

HOME

Harvey Friedman, in his paper Finite functions and the necessary use of large cardinals, Ann. of Math. 148:803-893, 1998, and in his technical report, Applications of large cardinals to graph theory, Dept. Math. Ohio State Univ, presents numerous combinatorial statements with clear geometric meaning that are proved using large cardinals and shown to require them. Of particular interest to us is Friedman's ZFC independent Jump Free Theorem proved in the technical report. In the discussion that follows, we discuss two papers that relate the Jump Free Theorem to the classical NP-complete subset sum problem.

(1) SUBSET SUM INSTANCES IN ZFC LIMBO: arXive:2012.05385v1 [math.CO] 10 Dec. 2020 This short paper introduces the Jump Free Theorem and presents a straightforward technique for relating it to the subset sum problem. It should be read first.

SUBSET SUM INSTANCES IN ZFC LIMBO

(2) ON THE DIFFICULTY OF PROVING P=NP IN ZFC. This paper, a slight extension of COMBINATORICS IN ZFC LIMBO, JOC VOLUME 10 NUMBER 3, 579-593, 2019, shows how recursive algorithms on directed lattice graphs, originally studied because of their interest in algorithmic combinatorics and in the study of large scale regularities of lattice embeddings of posets, connect with the Jump Free Theorem. A key algorithmic link is through the “committee model,” originally used as examples of how information flows upward through a model of a bureaucracy.

ON THE DIFFICULTY OF PROVING P=NP IN ZFC

Below we present, without further comments, a hint of the interesting combinatorial ideas involved in (2) above. This material is accessible to beginning graduate students in combinatorics, except for the advanced set theory whicn can be accepted without proof at first reading.

RegRegE
JumpFree001
PequalNP011
Defs
RegReg
Thm67