Recognition of tractable satisfiability problems through balanced polynomial representations

DOI10.1016/S0166-218X(99)00135-3zbMATH Open0943.68061WikidataQ126437746 ScholiaQ126437746MaRDI QIDQ1962045FDOQ1962045

Authors Joost P. Warners, Hans van Maaren 

Publication date 20 March 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

satisfiabilityDIMACS benchmarks

Mathematics Subject Classification ID

Recommendations

• Polynomially solvable satisfiability problems
• Complexity of satisfiability problems with symmetric polynomial clauses
• A perspective on certain polynomial-time solvable classes of satisfiability
• scientific article; zbMATH DE number 4023248
• Hierarchies of polynomially solvable satisfiability problems
• A hierarchy of tractable satisfiability problems
• The Structure of Tractable Constraint Satisfaction Problems
• Satisfiability problem: Some polynomial classes of conjunctive normal forms
• Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
• Fixed-parameter tractable reductions to SAT

Cites Work

• scientific article; zbMATH DE number 1348469 (Why is no real title available?)
• scientific article; zbMATH DE number 1114011 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• scientific article; zbMATH DE number 956858 (Why is no real title available?)
• A Complexity Index for Satisfiability Problems
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A two-phase algorithm for solving a class of hard satisfiability problems
• Elliptic approximations of propositional formulae
• Extended Horn sets in propositional logic
• Hard examples for resolution
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On renamable Horn and generalized Horn functions
• Polynomially solvable satisfiability problems
• Solving satisfiability problems using elliptic approximations -- effective branching rules
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited In (3)

• Solving satisfiability problems using elliptic approximations -- effective branching rules
• A two-phase algorithm for solving a class of hard satisfiability problems
• Balancedness of MSO transductions in polynomial time

Uses Software

• DIMACS

This page was built for publication: Recognition of tractable satisfiability problems through balanced polynomial representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962045)