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

computational complexityconstraint satisfaction problempropositional satisfiabilityclone theory

Mathematics Subject Classification ID

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

Cites work

• 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?)
• A Characterisation of First-Order Constraint Satisfaction Problems
• A First-Order Isomorphism Theorem
• A compendium of problems complete for symmetric logarithmic space
• 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
• 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 Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• The complexity of satisfiability problems
• The complexity theory companion
• The method of forced enumeration for nondeterministic automata
• Undirected ST-connectivity in log-space
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems

Cited in

(21)

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

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)