"Sets of Instances to Subset Sum Target Zero that are Solvable in Polynomial Time but Very Hard to Find"
Gill Williamson (UCSD)
Monday, October 11th 2021, 2-3pm
Abstract:
Our main result, shows the existence of a vast infinity of mysterious subset sum problems solvable in polynomial time. The only proof we have of this result uses the ZFC independent Jump Free Theorem of Friedman. The mathematics we use is elementary and at the level of good undergraduate courses in combinatorics (CSE 21) and design and analysis of algorithms (CSE 101). The statement of the Jump Free Theorem is also easily understood at this level (but not the proof). Wikipedia has a good discussion of ZFC independence. Further general discussion is available on my CSE website.