Parameterized Bounded-Depth Frege Is Not Optimal
From MaRDI portal
Publication:3012838
DOI10.1007/978-3-642-22006-7_53zbMath1334.03056WikidataQ59903065 ScholiaQ59903065MaRDI QIDQ3012838
Olaf Beyersdorff, Massimo Lauria, Alexander A. Razborov, Nicola Galesi
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
03F20: Complexity of proofs
Related Items
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