Lower bounds for bounded depth Frege proofs via Pudlák-Buss games

DOI10.1145/1740582.1740587zbMath1352.03065OpenAlexW1990362734MaRDI QIDQ2946607

Prahladh Harsha, Eli Ben-Sasson

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1740582.1740587

zbMATH Keywords

lower boundsproof complexityFrege proofspigeonhole principle

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (3)

A game characterisation of tree-like Q-resolution size ⋮ Partially definable forcing and bounded arithmetic ⋮ A Game Characterisation of Tree-like Q-resolution Size

This page was built for publication: Lower bounds for bounded depth Frege proofs via Pudlák-Buss games