2 citations · 4 across the 2 of their papers we have counts for
Showing math.COShow all
3 papers · 1 filter
math.CO2020
Subset Sum Instances in ZFC Limbo
S. Gill Williamson
Our main result, Theorem 2.5, shows the existence of a vast infinity of subset sum problems solvable in polynomial time. The only proof we have of this result uses the ZFC independ…
math.CO2019
On the difficulty of proving P equals NP in ZFC
S. Gill Williamson
Harvey Friedman, in his remarkable paper Finite functions and the necessary use of large cardinals, Ann. Math. 148:803-893, 1998 and in a technical report, Applications of large ca…
math.CO2017★ 2 cited
ZFC independence and subset sum
S. Gill Williamson
We study recursively defined functions associated with directed graphs on the k dimensional nonnegative integral lattice. The existence of certain combinatorial structures associat…