NP-Completeness of Refutability by Literal-Once Resolution

No abstract is available for this paper.

• Publication year

  2001

• Venue

  International Joint Conference on Automated Reasoning

• Publication date

  2001-06-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-45744-5_13
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference

  2002cited by this paper
• On subclasses of minimal unsatisfiable formulas

  2000cited by this paper
• An application of matroid theory to the SAT problem

  2000influential reference
• Propositional Logic: Deduction and Algorithms

  1999cited by this paper
• Intractability of read-once resolution

  1995influential reference
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas

  1986influential reference
• The complexity of facets resolved

  1985cited by this paper
• The Intractability of Resolution

  1985cited by this paper
• On Matrices with Connections

  1981cited by this paper
• On the Complexity of Regular Resolution and the Davis-Putnam Procedure

  1977cited by this paper
• A Machine-Oriented Logic Based on the Resolution Principle

  1965cited by this paper

• Analyzing Read-Once Cutting Plane Proofs in Horn Systems

  2022cites this paper
• On the lengths of tree-like and Dag-like cutting plane refutations of Horn constraint systems

  2022cites this paper
• Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas

  2021cites this paper
• Minimal Unsatisfiability and Autarkies

  2021cites this paper
• NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability

  2020cites this paper
• New Results on Cutting Plane Proofs for Horn Constraint Systems

  2019cites this paper
• A Polynomial Time Algorithm for Read-Once Certification of Linear Infeasibility in UTVPI Constraints

  2019cites this paper
• Read-Once Resolutions in Horn Formulas

  2019cites this paper
• Finding read-once resolution refutations in systems of 2CNF clauses

  2018cites this paper
• On the Computational Complexity of Read once Resolution Decidability in 2CNF Formulas

  2016influential citation
• Pool resolution is NP-hard to recognize

  2009cites this paper
• Mathematical Logic Pool resolution is NP-hard to recognize

  2009cites this paper
• The NP-hardness of finding a directed acyclic graph for regular resolution

  2008cites this paper
• Complexities of Homomorphism and Isomorphism for Definite Logic Programs

  2005cites this paper
• Theory and Applications of Satisfiability Testing

  2003cites this paper
• Lean clause-sets: generalizations of minimally unsatisfiable clause-sets

  2003cites this paper
• Homomorphisms of conjunctive normal forms

  2003cites this paper
• Read-Once Unit Resolution

  2003cites this paper
• A Bibliography of Papers in Lecture Notes in Computer Science (2001) (Part 2 of 4)

  year unknowncites this paper