A perspective on certain polynomial-time solvable classes of satisfiability
type: Item
instance of: scholarly article
title: A perspective on certain polynomial-time solvable classes of satisfiability
zbMATH Open document ID: 1012.68085
DOI: 10.1016/S0166-218X(01)00358-4
published in: Discrete Applied Mathematics
publication date: 2003-03-09T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1878518
zbMATH Keywords: satisfiability
zbMATH Keywords: random CNF formulas
zbMATH Keywords: matching
zbMATH Keywords: NP-complete
zbMATH Keywords: probabilistic analysis
author: John V. Franco
author: Allen Van Gelder
describes a project that uses: DIMACS
describes a project that uses: Leibniz
MaRDI profile type: Publication
cites work: Q3661894
cites work: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
cites work: Q4004078
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: Recognizing disguised NR(1) instances of the satisfiability problem
cites work: Q4542576
cites work: Q3682518
cites work: Recognition of \(q\)-Horn formulae in linear time
cites work: A Complexity Index for Satisfiability Problems
cites work: Q3140436
cites work: Extended Horn sets in propositional logic
cites work: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
cites work: Q4228436
cites work: Many hard examples for resolution
cites work: A hierarchy of tractable satisfiability problems
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Q4375759
cites work: Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
cites work: Analysis of Two Simple Heuristics on a Random Instance ofk-sat
cites work: A threshold for unsatisfiability
cites work: On Representatives of Subsets
cites work: A Proof Procedure Using Connection Graphs
cites work: Investigations on autark assignments
cites work: Renaming a Set of Clauses as a Horn Set
cites work: A short note on some tractable cases of the satisfiability problem.
cites work: The complexity of satisfiability problems
cites work: On finding solutions for extended Horn formulas
cites work: A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
cites work: A simplified NP-complete satisfiability problem
cites work: Q4705311
cites work: Q5687274
Recommended article: Q4375759
Recommended article: Polynomially solvable satisfiability problems
Recommended article: Hierarchies of polynomially solvable satisfiability problems
Recommended article: Polynomial-average-time satisfiability problems
Recommended article: Complexity of satisfiability problems with symmetric polynomial clauses
Recommended article: Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
Recommended article: Parameterized and subexponential-time complexity of satisfiability problems and applications
Recommended article: On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Recommended article: Mathematical Foundations of Computer Science 2005
Recommended article: Q3606145
description: scientific article; zbMATH DE number 1878518