Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets

DOI10.3792/pjaa.84.159zbMath1157.03034OpenAlexW2038549427MaRDI QIDQ2378659

Akihiro Nozaki, Noriko H. Arai, Toshiyasu Arai

Publication date: 13 January 2009

Published in: Proceedings of the Japan Academy. Series A (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.pja/1223299526

zbMATH Keywords

Frege systemtrace of setslengths of proofs

Mathematics Subject Classification ID

Extremal set theory (05D05) Complexity of proofs (03F20)

Related Items (2)

QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

• Unnamed Item
• Unnamed Item
• On the trace of finite sets
• A bounded arithmetic AID for Frege systems

This page was built for publication: Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets