Quantified Constraints in Twenty Seventeen
From MaRDI portal
Publication:4993605
DOI10.4230/DFU.Vol7.15301.327zbMath1482.68168OpenAlexW2592947705MaRDI QIDQ4993605
Publication date: 15 June 2021
Full work available at URL: https://doi.org/10.4230/DFU.Vol7.15301.12
computational complexityconstraint satisfaction problemsuniversal algebraparameterized complexityquantified constraints
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)
Related Items
Constraint satisfaction problem: what makes the problem easy, Surjective polymorphisms of directed reflexive cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Quantified constraint satisfaction and the polynomially generated powers property
- Maltsev digraphs have a majority polymorphism
- The complexity of constraint satisfaction games and QCSP
- Existence theorems for weakly symmetric operations
- Existentially restricted quantified constraint satisfaction
- Relatively quantified constraint satisfaction
- On the complexity of H-coloring
- From local to global consistency
- Graphs with edge-preserving majority functions
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- A new tractable class of constraint satisfaction problems
- Resolution for quantified Boolean formulas
- Weak near-unanimity functions and digraph homomorphism problems
- On Maltsev digraphs
- Solving quantified constraint satisfaction problems
- Bounded-width QBF is PSPACE-complete
- Combinatorial problems raised from 2-semilattices
- Dichotomy for finite tournaments of mixed-type
- Closed systems of functions and predicates
- Quantified conjunctive queries on partially ordered sets
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Extending the Notion of Preferred Explanations for Quantified Constraint Satisfaction Problems
- Schaefer's Theorem for Graphs
- On Sequent Systems and Resolution for QBFs
- Meditations on Quantified Constraint Satisfaction
- Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems
- Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
- Generalizing consistency and other constraint properties to quantified constraints
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction
- Retractions to Pseudoforests
- QCSP on Partially Reflexive Forests
- The Complexity of Counting Quantifiers on Equality Languages
- Quantified Constraints and Containment Problems
- Constraint Satisfaction with Countable Homogeneous Templates
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- Quantified Positive Temporal Constraints
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of temporal constraint satisfaction problems
- Resolution and Expressiveness of Subclasses of Quantified Boolean Formulas and Circuits
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Complexity of Colouring by Semicomplete Digraphs
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Reasoning about temporal relations
- Model checking existential logic on partially ordered sets
- The tractability frontier of graph-like first-order query sets
- From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP
- QCSP on Partially Reflexive Cycles – The Wavy Line of Tractability
- QCSP on Semicomplete Digraphs
- Tractability of quantified temporal constraints to the max
- When is the evaluation of conjunctive queries tractable?
- Constraint Satisfaction with Counting Quantifiers
- Classifying the Complexity of Constraints Using Finite Algebras
- Block-Sorted Quantified Conjunctive Queries
- Quantified Equality Constraints
- Computer Science Logic
- The complexity of satisfiability problems
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates
- A Machine-Oriented Logic Based on the Resolution Principle
- Reduced Products and Horn Classes
- A Computing Procedure for Quantification Theory
- STACS 2005
- Logical Approaches to Computational Barriers
- Principles and Practice of Constraint Programming – CP 2004
