QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS

DOI10.1017/jsl.2015.17zbMath1436.03298OpenAlexW2460222798WikidataQ113858289 ScholiaQ113858289MaRDI QIDQ3188337

James Aisenberg, Maria Luisa Bonet, Samuel R. Buss

Publication date: 19 August 2016

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2117/100899

zbMATH Keywords

Kruskal-Katona theoremFrege proofstrace of setsextended Frege proofsFrankl's theoremhereditary matrix

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (4)

Short Proofs of the Kneser-Lovász Coloring Principle ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Propositional consistency proofs
• On the trace of finite sets
• Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets

This page was built for publication: QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS