The Complexity of Finding Read-Once NAE-Resolution Refutations

DOI10.1007/978-3-662-54069-5_6zbMath1483.68145OpenAlexW2559110068MaRDI QIDQ5224491

Hans Kleine Büning, K. Subramani and Vahan Mkrtchyan, Piotr J. Wojciechowski

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

refutationread-onceNAE-SAToptimal-length refutation

Mathematics Subject Classification ID

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

Related Items

Copy complexity of Horn formulas with respect to unit read-once resolution ⋮ NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

Cites Work

• On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas
• The complexity of satisfiability problems
• The Complexity of Propositional Proofs
• A Machine-Oriented Logic Based on the Resolution Principle
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Complexity of Finding Read-Once NAE-Resolution Refutations