On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas

DOI10.1007/978-3-319-55911-7_26zbMath1485.68110arXiv1610.04523OpenAlexW2533102354MaRDI QIDQ2988835

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

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.04523

zbMATH Keywords

resolution2SATread-once

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35) Structure of proofs (03F07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (1)

The Complexity of Finding Read-Once NAE-Resolution Refutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• The complexity of facets resolved
• The directed subgraph homeomorphism problem
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• On the structure of some classes of minimal unsatisfiable formulas
• The complexity of read-once resolution
• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
• On the Complexity of Timetable and Multicommodity Flow Problems
• The Complexity of Propositional Proofs
• A Machine-Oriented Logic Based on the Resolution Principle

This page was built for publication: On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas