The complexity of satisfiability problems: Refining Schaefer's theorem

DOI10.1016/J.JCSS.2008.11.001MaRDI QIDQ1015812zbMATH OpenOpenAlexFDO

Authors Michael Bauland, Henning Schnoor, Heribert Vollmer, Eric Allender, Neil Immerman

Publication date 30 April 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.11.001

zbMATH Keywords

clone theorycomputational complexityconstraint satisfaction problempropositional satisfiability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites work

• A Characterisation of First-Order Constraint Satisfaction Problems
• A compendium of problems complete for symmetric logarithmic space
• A First-Order Isomorphism Theorem
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Bases for Boolean co-clones
• Closed systems of functions and predicates
• Closure properties of constraints
• Complexity classifications of Boolean constraint satisfaction problems
• Function Algebras on Finite Sets
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1061261 (Why is no real title available?)
• scientific article; zbMATH DE number 2081094 (Why is no real title available?)
• Linear Datalog and Bounded Path Duality of Relational Structures
• Mathematical Foundations of Computer Science 2005
• Nondeterministic Space is Closed under Complementation
• On digraph coloring problems and treewidth duality
• Resolution for quantified Boolean formulas
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• The complexity of satisfiability problems
• The complexity theory companion
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The method of forced enumeration for nondeterministic automata
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Undirected ST-connectivity in log-space
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems

Cited in

(24)

• Bases for Boolean co-clones
• Axiomatisability and hardness for universal Horn classes of hypergraphs
• Two-element structures modulo primitive positive constructability
• Weak bases of Boolean co-clones
• Satisfiability with index dependency
• scientific article; zbMATH DE number 1688380 (Why is no real title available?)
• Finding Reductions Automatically
• A Complexity Index for Satisfiability Problems
• Shiner–Davison–Landsberg complexity revisited
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Computing kernels in parallel: lower and upper bounds
• Proof Complexity for the Maximum Satisfiability Problem and its Use in SAT Refutations
• Complexity and polymorphisms for digraph constraint problems under some basic constructions
• An algebraic characterization of testable Boolean CSPs
• Learnability of solutions to conjunctive queries
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• Forbidden tournaments and the orientation completion problem
• A topological version of Schaefer's dichotomy theorem
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• The complexity of the list homomorphism problem for graphs
• NP-completeness by first-order and quantifier-free interpretations and related topics
• Quantum sat problems with finite sets of projectors are complete for a plethora of classes
• The complexity of equality constraint languages

This page was built for publication: The complexity of satisfiability problems: Refining Schaefer's theorem

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