The complexity of satisfiability problems: Refining Schaefer's theorem

No abstract is available for this paper.

• Publication year

  2005

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  2005-08-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jcss.2008.11.001
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Introduction to Circuit Complexity: A Uniform Approach

  2010cited by this paper
• Universal algebra and hardness results for constraint satisfaction problems

  2007cited by this paper
• Function algebras on finite sets : a basic course on many-valued logic and clone theory

  2006cited by this paper
• The Complexity of Constraint Languages

  2006cited by this paper
• Handbook of Constraint Programming

  2006cited by this paper
• Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory (Springer Monographs in Mathematics)

  2006cited by this paper
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

  2006cited by this paper
• A Characterisation of First-Order Constraint Satisfaction Problems

  2006cited by this paper
• Undirected ST-connectivity in log-space

  2005influential reference
• On digraph coloring problems and treewidth duality

  2005cited by this paper
• Linear datalog and bounded path duality of relational structures

  2005cited by this paper
• Bases for Boolean co-clones

  2005cited by this paper
• Existential positive types and preservation under homomorphisms

  2005cited by this paper
• SIGACT news complexity theory column 48

  2005cited by this paper
• The Complexity of Satisabilit y Problems: Rening Schaefer's Theorem

  2004cited by this paper
• Quantum search algorithms

  2004cited by this paper
• Playing with Boolean Blocks , Part II : Constraint Satisfaction Problems 1

  2004cited by this paper
• SIGACT news complexity theory column 43

  2004cited by this paper
• A dichotomy theorem for constraints on a three-element set

  2002cited by this paper
• The complexity theory companion

  2001cited by this paper
• The First-Order Isomorphism Theorem

  2001cited by this paper
• Generalized satisfiability problems

  2001cited by this paper
• Hard Sets and Pseudo-random Generators for Constant Depth Circuits

  2001cited by this paper
• Complexity classifications of Boolean constraint satisfaction problems

  2001cited by this paper
• A compendium of problems complete for symmetric logarithmic space

  2000cited by this paper
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

  1999cited by this paper
• Descriptive Complexity

  1999cited by this paper
• Theories of computability

  1997cited by this paper
• Closure properties of constraints

  1997cited by this paper
• Gap-Languages and Log-Time Complexity Classes

  1997cited by this paper
• Pure versus impure Lisp

  1996cited by this paper
• Resolution for Quantified Boolean Formulas

  1995cited by this paper
• A First-Order Isomorphism Theorem

  1993cited by this paper
• Nondeterministic space is closed under complementation

  1988influential reference
• The method of forced enumeration for nondeterministic automata

  1988influential reference
• A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas

  1979cited by this paper
• The complexity of satisfiability problems

  1978influential reference
• CLOSED SYSTEMS OF FUNCTIONS AND PREDICATES

  1968cited by this paper
• The two-valued iterative systems of mathematical logic

  1942cited by this paper

• On Important Applications of Special Set Decomposition

  2026cites this paper
• A Dichotomy Theorem for Automatic Structures

  2026influential citation
• Modal Fragments

  2026cites this paper
• Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

  2025cites this paper
• Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization

  2024cites this paper
• A Topological Version of Schaefer's Dichotomy Theorem

  2023cites this paper
• Constant-depth circuits vs. monotone circuits

  2023cites this paper
• Forbidden Tournaments and the Orientation Completion Problem

  2023cites this paper
• Artificial dragonfly algorithm in the Hopfield neural network for optimal Exact Boolean k satisfiability representation

  2023cites this paper
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

  2022cites this paper
• Constraint Satisfaction Problems Lecture Notes

  2022cites this paper
• Complexity of Infinite-Domain Constraint Satisfaction

  2021cites this paper
• Quantum Constraint Problems can be complete for BQP, QCMA, and more

  2021cites this paper
• Digraph homomorphism problem and weak near unanimity polymorphism.

  2020cites this paper
• A dichotomy theorem for nonuniform CSPs simplified

  2020cites this paper
• Ontology-Mediated Querying with Horn Description Logics

  2020cites this paper
• CSPs with global modular constraints: algorithms and hardness via polynomial representations

  2019cites this paper
• The Complexity of Finding S-factors in Regular Graphs

  2019cites this paper
• Two-element structures modulo primitive positive constructability

  2019influential citation
• A Hypergraph Based Approach for the 4-Constraint Satisfaction Problem Tractability

  2019cites this paper
• The complexity of class L

  2019influential citation
• Necessary and sufficient conditions for Boolean satisfiability

  2019cites this paper
• On the complexity of ℍ-coloring for special oriented trees

  2018cites this paper
• 2 O ct 2 01 7 On the complexity of H-coloring for special oriented trees

  2018cites this paper
• Constraint satisfaction problems: complexity and algorithms

  2018influential citation
• XX : 2 Fixed-parameter Approximability of Boolean MinCSPs 1

  2018cites this paper
• Computing Kernels in Parallel: Lower and Upper Bounds

  2018cites this paper
• Polymorphisms, and How to Use Them

  2017cites this paper
• The Complexity of Resilience

  2017cites this paper
• A Dichotomy Theorem for Nonuniform CSPs

  2017cites this paper
• The Constraint Satisfaction Problem: Complexity and Approximability

  2017cites this paper
• Algebra and the Complexity of Digraph CSPs: a Survey

  2017cites this paper
• Zeons, Orthozeons, and Graph Colorings

  2017cites this paper
• Strong partial clones and the time complexity of SAT problems

  2017cites this paper
• Dichotomy for Digraph Homomorphism Problems (two algorithms)

  2017cites this paper
• Synthesising executable gene regulatory networks in haematopoiesis from single-cell gene expression data

  2017influential citation
• Axiomatisability and hardness for universal Horn classes of hypergraphs

  2017cites this paper
• Dichotomy for Digraph Homomorphism Problems

  2017cites this paper
• The Data Complexity of Description Logic Ontologies

  2016cites this paper
• All or Nothing: Toward a Promise Problem Dichotomy for Constraint Problems

  2016cites this paper
• Asking the Metaquestions in Constraint Tractability

  2016cites this paper
• Fixed-parameter Approximability of Boolean MinCSPs

  2016cites this paper
• Zeons, Orthozeons, and Graph Colorings

  2016cites this paper
• Impossibility Theorems and the Universal Algebraic Toolkit

  2015cites this paper
• Learnability of Solutions to Conjunctive Queries: The Full Dichotomy

  2015cites this paper
• Defining Asymptotic Parallel Time Complexity of Data-dependent Algorithms

  2014cites this paper
• Problèmes d'homomorphisme à largeur de chemin bornée

  2014cites this paper
• Existential Second-Order Logic Over Graphs: A Complete Complexity-Theoretic Classification

  2014cites this paper
• The complexity of satisfaction problems in reverse mathematics

  2014cites this paper
• Conception et analyse des biopuces à ADN en environnements parallèles et distribués. (Design and analysis of DNA microarrays in parallel and distributed environments)

  2014cites this paper
• A new greedy randomised adaptive search procedure for solving the maximum satisfiability problem

  2013cites this paper
• Weak bases of Boolean co-clones

  2013cites this paper
• On constraint satisfaction problems below P

  2013cites this paper
• Complexity Classifications for Logic-Based Argumentation

  2013cites this paper
• Complexity and polymorphisms for digraph constraint problems under some basic constructions

  2013influential citation
• Digraph related constructions and the complexity of digraph homomorphism problems

  2013cites this paper
• An Algebraic Characterization of Testable Boolean CSPs

  2013cites this paper
• A pr 2 01 3 Complexity Classifications for logic-based Argumentation

  2013cites this paper
• Complexity Classification in Infinite-Domain Constraint Satisfaction

  2012cites this paper
• Non-Uniform Data Complexity of Query Answering in Description Logics

  2012cites this paper
• Complexité des homomorphismes de graphes avec listes

  2012cites this paper
• Results on Extensions of the Satisfiability Problem

  2012cites this paper
• An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

  2012cites this paper
• Le problème de décision CSP : homomorphismes et espace logarithmique

  2012cites this paper
• Near Unanimity Constraints Have Bounded Pathwidth Duality

  2012cites this paper
• On the Expression Complexity of Equivalence and Isomorphism of Primitive Positive Formulas

  2012cites this paper
• Minimization for Generalized Boolean Formulas

  2011cites this paper
• Finding Reductions Automatically

  2010cites this paper
• Satisfiability with Index Dependency

  2010influential citation
• The Complexity of Problems for Quantified Constraints

  2010influential citation
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint

  2010cites this paper
• Extremal colorings and extremal satisfiability

  2010cites this paper
• Constraint satisfaction problems and global cardinality constraints

  2010cites this paper
• Extremal Colorings and

  2009cites this paper
• The Complexity of the List Homomorphism Problem for Graphs

  2009cites this paper
• A rendezvous of logic, complexity, and algebra

  2009cites this paper
• Worst-Case Upper Bounds

  2009cites this paper
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

  2008cites this paper
• Recent Results on the Algebraic Approach to the CSP

  2008cites this paper
• Boolean Constraint Satisfaction Problems: When Does Post's Lattice Help?

  2008cites this paper
• Partial Polymorphisms and Constraint Satisfaction Problems

  2008cites this paper
• Computational Complexity of Constraint Satisfaction

  2007cites this paper
• Complexity results for boolean constraint satisfaction problems

  2007cites this paper
• Universal algebra and hardness results for constraint satisfaction problems

  2007influential citation
• Complexity Results for Boolean Constraint Satisfaction Problems

  2007cites this paper
• Enumerating All Solutions for Constraint Satisfaction Problems

  2007cites this paper
• Symmetric Datalog and Constraint Satisfaction Problems in Logspace

  2007influential citation
• The Complexity of Equality Constraint Languages

  2006cites this paper
• A rendezvous of logic, complexity, and algebra

  2006cites this paper
• Logic Column 17: A Rendezvous of Logic, Complexity, and Algebra

  2006cites this paper