The complexity of finding read-once NAE-resolution refutations

DOI10.1007/978-3-662-54069-5_6MaRDI QIDQ5224491zbMATH OpenOpenAlexFDO

Authors Hans Kleine Büning, Piotr Wojciechowski, K. Subramani

Publication date 24 July 2019

Published in Logic and Its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-54069-5_6

zbMATH Keywords

NAE-SAToptimal-length refutationread-oncerefutation

Mathematics Subject Classification ID

Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
• Finding read-once resolution refutations in systems of 2CNF clauses
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• The complexity of read-once resolution
• On the computational complexity of read once resolution decidability in 2CNF formulas

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• scientific article; zbMATH DE number 5539366 (Why is no real title available?)
• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• scientific article; zbMATH DE number 1342249 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1179974 (Why is no real title available?)
• On the computational complexity of read once resolution decidability in 2CNF formulas
• The Complexity of Propositional Proofs
• The complexity of satisfiability problems
• The nature of computation

Cited in

(8)

• The complexity of read-once resolution
• Finding read-once resolution refutations in systems of 2CNF clauses
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas
• Copy complexity of Horn formulas with respect to unit read-once resolution
• On the computational complexity of read once resolution decidability in 2CNF formulas
• NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
• scientific article; zbMATH DE number 1765669 (Why is no real title available?)
• Theory and Applications of Satisfiability Testing

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

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