Parameterized Bounded-Depth Frege Is Not Optimal

DOI10.1007/978-3-642-22006-7_53zbMath1334.03056WikidataQ59903065 ScholiaQ59903065MaRDI QIDQ3012838

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

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.225.6190

Mathematics Subject Classification ID

03F20: Complexity of proofs

Related Items

Parameterized Complexity of DPLL Search Procedures

Cites Work

• Parameterized proof complexity
• Exponential lower bounds for the pigeonhole principle
• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• The intractability of resolution
• Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
• A complexity gap for tree resolution
• Describing parameterized complexity classes
• The parameterized complexity of maximality and minimality problems
• The resolution complexity of independent sets and vertex covers in random graphs
• The Efficiency of Resolution and Davis--Putnam Procedures
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• Parameterized Complexity of DPLL Search Procedures