The complexity of read-once resolution

DOI10.1023/A:1016339119669MaRDI QIDQ1610491zbMATHOpenAlexFDO

Authors Hans Kleine Büning, Xishun Zhao

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)

Recommendations

• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 1765669
• The complexity of finding read-once NAE-resolution refutations
• On the computational complexity of read once resolution decidability in 2CNF formulas
• The complexity of some subclasses of minimal unsatisfiable formulas.

Cited in

(14)

• Are hitting formulas hard for resolution?
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• Copy complexity of Horn formulas with respect to unit read-once resolution
• On the computational complexity of read once resolution decidability in 2CNF formulas
• On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
• Proving the infeasibility of Horn formulas through read-once resolution
• The complexity of finding read-once NAE-resolution refutations
• Constrained read-once refutations in UTVPI constraint systems: a parallel perspective
• Theory and Applications of Satisfiability Testing
• Finding read-once resolution refutations in systems of 2CNF clauses
• NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
• Analyzing read-once cutting plane proofs in Horn systems
• On exact selection of minimally unsatisfiable subformulae
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1610491)