scientific article; zbMATH DE number 1179974

zbMath0908.68164MaRDI QIDQ4399249

Toniann Pitassi, P. W. Beame

Publication date: 14 March 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

propositional logicproof systems

Mathematics Subject Classification ID

Related Items (23)

Narrow Proofs May Be Maximally Long ⋮ Resolution lower bounds for perfect matching principles ⋮ A unified framework for DPLL(T) + certificates ⋮ Proof compressions with circuit-structured substitutions ⋮ Optimal length resolution refutations of difference constraint systems ⋮ A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ Resolution lower bounds for the weak functional pigeonhole principle. ⋮ On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas ⋮ Unnamed Item ⋮ Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints ⋮ Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ Finding read-once resolution refutations in systems of 2CNF clauses ⋮ The complexity of the Hajós calculus for planar graphs ⋮ Mean-payoff games and propositional proofs ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability ⋮ The Complexity of Finding Read-Once NAE-Resolution Refutations ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Short Proofs for the Determinant Identities ⋮ A syntactical proof of the Marriage Lemma. ⋮ Unrestricted vs restricted cut in a tableau method for Boolean circuits ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Two party immediate response disputes: Properties and efficiency

This page was built for publication: