Complexity Classifications of Boolean Constraint Satisfaction Problems
From MaRDI portal
Publication:2723175
DOI10.1137/1.9780898718546zbMath0981.68058OpenAlexW1571873445MaRDI QIDQ2723175
Sanjeev Khanna, Madhu Sudan, Nadia Creignou
Publication date: 3 July 2001
Full work available at URL: https://doi.org/10.1137/1.9780898718546
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs ⋮ The complexity of counting locally maximal satisfying assignments of Boolean CSPs ⋮ Concise finite-domain representations for PDDL planning tasks ⋮ The complexity of minimal satisfiability problems ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations ⋮ The complexity of constraint satisfaction games and QCSP ⋮ On the Complexity of the Model Checking Problem ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ The Expressive Power of Binary Submodular Functions ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Solving quantified constraint satisfaction problems ⋮ Quantum machine learning: a classical perspective ⋮ On planar valued CSPs ⋮ Modularity-based decompositions for valued CSP ⋮ Paradigms for parameterized enumeration ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ Improved Computational Approaches and Heuristics for Zero Forcing ⋮ Universal qudit Hamiltonians ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Classes of submodular constraints expressible by graph cuts ⋮ Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights ⋮ On the Boolean connectivity problem for Horn relations ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Multiaffinity testing of Boolean functions using their Zhegalkin polynomials ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ An upper (lower) bound for Max (Min) CSP ⋮ First-Order Model Checking Problems Parameterized by the Model ⋮ Generalized satisfiability problems: Minimal elements and phase transitions. ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ Majority constraints have bounded pathwidth duality ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ A complete 4-parametric complexity classification of short shop scheduling problems ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ The Expressive Power of Valued Constraints: Hierarchies and Collapses ⋮ Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems ⋮ The complexity of surjective homomorphism problems-a survey ⋮ The complexity of problems for quantified constraints ⋮ Colouring, constraint satisfaction, and complexity ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ The Complexity of Valued CSPs ⋮ The complexity of equality constraint languages ⋮ Quantified Constraints in Twenty Seventeen ⋮ On the Complexity of Holant Problems ⋮ Computational complexity of auditing finite attributes in statistical databases ⋮ Search techniques for SAT-based Boolean optimization ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ An algebraic hardness criterion for surjective constraint satisfaction. ⋮ Boolean max-co-clones ⋮ Temporal network optimization subject to connectivity constraints ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ Colocating tasks in data centers using a side-effects performance model ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ Trichotomies in the complexity of minimal inference ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Complexity of clausal constraints over chains ⋮ A computational proof of complexity of some restricted counting problems ⋮ The Helly property and satisfiability of Boolean formulas defined on set families ⋮ The expressive power of binary submodular functions ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ Approximability of clausal constraints ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ An approximation trichotomy for Boolean \#CSP ⋮ Combinatorial method for solving systems of linear constraints ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Isomorphic implication ⋮ The complexity of Boolean constraint satisfaction local search problems ⋮ CSP duality and trees of bounded pathwidth ⋮ A note on some collapse results of valued constraints ⋮ Unnamed Item ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ Complexity Classification of Local Hamiltonian Problems ⋮ As Close as It Gets ⋮ On the computation of the Möbius transform ⋮ Existentially restricted quantified constraint satisfaction ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Relatively quantified constraint satisfaction ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Multiaffine polynomials over a finite field ⋮ Minimal distance of propositional models ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Bases for Boolean co-clones ⋮ The expressive rate of constraints ⋮ A dichotomy for real weighted Holant problems ⋮ Periodic constraint satisfaction problems: Tractable subclasses ⋮ \(H\)-coloring dichotomy revisited ⋮ The Complexity of General-Valued CSPs ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Tractability of explaining classifier decisions ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Классы Шефера, классы Поста и соответствия Галуа ⋮ Стабилизаторы некоторых семейств булевых функций, образующих Галуа-замкнутые подалгебры алгебры Шефера ⋮ The Next Whisky Bar ⋮ Tractability of quantified temporal constraints to the max ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Unnamed Item ⋮ Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ The Complexity of Quantified Constraints Using the Algebraic Formulation ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Basics of Galois Connections ⋮ Dualities for Constraint Satisfaction Problems ⋮ Introduction to the Maximum Solution Problem ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Uses Software
This page was built for publication: Complexity Classifications of Boolean Constraint Satisfaction Problems
