63 citations · 77 across the 15 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
cs.CC2007★ 63 cited
Resolution over Linear Equations and Multilinear Proofs
Ran Raz, Iddo Tzameret
We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead…
cs.CC2007
Complexity of Propositional Proofs under a Promise
Nachum Dershowitz, Iddo Tzameret
We study -- within the framework of propositional proof complexity -- the problem of certifying unsatisfiability of CNF formulas under the promise that any satisfiable formula has…