The complexity of read-once resolution

DOI10.1023/A:1016339119669zbMath1015.68081OpenAlexW1512384059MaRDI QIDQ1610491

Hans Kleine Büning, Zhao, Xishun

Publication date: 20 August 2002

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1016339119669

zbMATH Keywords

complexitypropositional formulasminimal unsatisfiability\(k\)-resolutionread-once resolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (10)

A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Are hitting formulas hard for resolution? ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas ⋮ Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ Finding read-once resolution refutations in systems of 2CNF clauses ⋮ On exact selection of minimally unsatisfiable subformulae ⋮ On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems ⋮ NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

This page was built for publication: The complexity of read-once resolution