Short resolution proofs for a sequence of tricky formulas

DOI10.1007/s002360050044zbMath0858.68092OpenAlexW2126362918MaRDI QIDQ1924995

Gunnar Stålmarck

Publication date: 27 October 1996

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s002360050044

zbMATH Keywords

propositional formulas

Mathematics Subject Classification ID

Related Items (13)

On the complexity of resolution with bounded conjunctions ⋮ A note about \(k\)-DNF resolution ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Regular and General Resolution: An Improved Separation ⋮ The treewidth of proofs ⋮ A simplified way of proving trade-off results for resolution ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ An Exponential Lower Bound for Width-Restricted Clause Learning ⋮ Sum of squares bounds for the ordering principle ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Separation results for the size of constant-depth propositional proofs ⋮ On Linear Resolution ⋮ Large clique is hard on average for resolution

Cites Work

• Unnamed Item
• Short proofs for tricky formulas
• The intractability of resolution
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• Über eine Art von Unvollständigkeit des Prädikatenkalküls der ersten Stufe

This page was built for publication: Short resolution proofs for a sequence of tricky formulas