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)

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

zbMATH Keywords

satisfiabilityDIMACS benchmarks

Mathematics Subject Classification ID

Cites Work

• Title not available (Why is that?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Hard examples for resolution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Extended Horn sets in propositional logic
• A Complexity Index for Satisfiability Problems
• On renamable Horn and generalized Horn functions
• Polynomially solvable satisfiability problems
• Title not available (Why is that?)
• A two-phase algorithm for solving a class of hard satisfiability problems
• Solving satisfiability problems using elliptic approximations -- effective branching rules
• Elliptic approximations of propositional formulae
• Title not available (Why is that?)

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)