Parameterized Bounded-Depth Frege Is not Optimal

DOI10.1145/2355580.2355582zbMath1322.68082OpenAlexW2092508401WikidataQ59902355 ScholiaQ59902355MaRDI QIDQ2947567

Massimo Lauria, Nicola Galesi, Olaf Beyersdorff, Alexander A. Razborov

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

resolutionproof complexityparameterized complexitybounded-depth Frege

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (7)

Narrow Proofs May Be Maximally Long ⋮ Proof complexity of modal resolution ⋮ Relativization makes contradictions harder for resolution ⋮ Tight size-degree bounds for sums-of-squares proofs ⋮ The complexity of proving that a graph is Ramsey ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Resolution and the binary encoding of combinatorial principles

This page was built for publication: Parameterized Bounded-Depth Frege Is not Optimal