A perspective on certain polynomial-time solvable classes of satisfiability
From MaRDI portal
Publication:1861558
DOI10.1016/S0166-218X(01)00358-4zbMath1012.68085MaRDI QIDQ1861558
Allen van Gelder, John V. Franco
Publication date: 9 March 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Properties of SLUR Formulae, Computing Maximal Autarkies with Few and Simple Oracle Queries, Generalising and Unifying SLUR and Unit-Refutation Completeness, Filter-based resolution principle for lattice-valued propositional logic LP\((X)\), A CNF Class Generalizing Exact Linear Formulas, An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF, Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets, Homomorphisms of conjunctive normal forms., A CNF Formula Hierarchy over the Hypercube, About some UP-based polynomial fragments of SAT, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, On exact selection of minimally unsatisfiable subformulae, Generalizations of matched CNF formulas, Linear CNF formulas and satisfiability, Unnamed Item, Investigations on autark assignments, Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency., Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference., The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Resolution complexity of random constraint satisfaction problems: Another half of the story, Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story, A perspective on certain polynomial-time solvable classes of satisfiability, Generalising unit-refutation completeness and SLUR via nested input resolution
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding solutions for extended Horn formulas
- A threshold for unsatisfiability
- A simplified NP-complete satisfiability problem
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- A hierarchy of tractable satisfiability problems
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Recognition of \(q\)-Horn formulae in linear time
- Investigations on autark assignments
- A short note on some tractable cases of the satisfiability problem.
- A perspective on certain polynomial-time solvable classes of satisfiability
- A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
- Many hard examples for resolution
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Recognizing disguised NR(1) instances of the satisfiability problem
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Proof Procedure Using Connection Graphs
- Renaming a Set of Clauses as a Horn Set
- A Complexity Index for Satisfiability Problems
- Extended Horn sets in propositional logic
- On Representatives of Subsets
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- The complexity of satisfiability problems
