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

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