scientific article; zbMATH DE number 1222561
From MaRDI portal
Publication:4218098
zbMath0911.03028MaRDI QIDQ4218098
Michael Alekhnovich, Toniann Pitassi, Shlomo Moran, Samuel R. Buss
Publication date: 2 March 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Structure of proofs (03F07) Complexity of proofs (03F20)
Related Items
Optimal length resolution refutations of difference constraint systems, A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints, Improved algorithms for optimal length resolution refutation in difference constraint systems, On the limit of branching rules for hard random unsatisfiable 3-SAT, PCP characterizations of NP: toward a polynomially-small error-probability, A combinatorial algorithm for Horn programs, Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints, Frugal Routing on Wireless Ad-Hoc Networks, NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability, On the hardness of approximating label-cover, On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations