The complexity of satisfiability problems: Refining Schaefer's theorem

DOI10.1016/j.jcss.2008.11.001zbMath1161.68487OpenAlexW2001101327MaRDI QIDQ1015812

Henning Schnoor, Neil Immerman, Michael Bauland, Heribert Vollmer, Eric W. Allender

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

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

Related Items (15)

Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Satisfiability with index dependency ⋮ Axiomatisability and hardness for universal Horn classes of hypergraphs ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Weak bases of Boolean co-clones ⋮ The complexity of equality constraint languages ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ The complexity of the list homomorphism problem for graphs ⋮ Finding Reductions Automatically ⋮ Unnamed Item ⋮ Two-element structures modulo primitive positive constructability ⋮ Bases for Boolean co-clones ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

Cites Work

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

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