Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets

DOI10.1017/JSL.2015.17zbMATH Open1436.03298OpenAlexW2460222798WikidataQ113858289 ScholiaQ113858289MaRDI QIDQ3188337FDOQ3188337

Authors: James Aisenberg, Maria Luisa Bonet, Samuel R. Buss 

Publication date: 19 August 2016

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

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

Recommendations

• scientific article; zbMATH DE number 806744
• Polynomial size proofs of the propositional pigeonhole principle
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Exponential lower bounds for the pigeonhole principle
• Quasipolynomial size proofs of the propositional pigeonhole principle

zbMATH Keywords

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

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cites Work

• On the trace of finite sets
• Propositional consistency proofs
• The provably total NP search problems of weak second order bounded arithmetic
• Title not available (Why is that?)
• Polynomal-size Frege proofs of Bollobás' theorem on the trace of sets

Cited In (4)

• Characterizing propositional proofs as noncommutative formulas
• Quasipolynomial size proofs of the propositional pigeonhole principle
• Short proofs of the Kneser-Lovász coloring principle
• Propositional proofs in Frege and extended Frege systems (abstract)

This page was built for publication: Quasipolynomial size Frege proofs of Frankl's theorem on the trace of sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188337)