Π₂^P vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem

2024/04/05 by Dmitriy Zhuk, Zhuk, Dmitriy · 1 voice
Computer Science · Engineering · Mathematics · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Optimization and Packing Problems #Scheduling and Optimization Algorithms #cs.CC #cs.LO #math.LO

paper · pdf · doi:10.48550/arxiv.2404.03844

openalex publication_date 2024/04/05 · arxiv published 2024/04/05 · openalex created_date 2024/04/09 · arxiv updated 2024/10/21 · openalex updated_date 2026/07/28

Abstract

The Quantified Constraint Satisfaction Problem is the problem of evaluating a sentence with both quantifiers, over relations from some constraint language, with conjunction as the only connective. We show that for any constraint language on a finite domain the Quantified Constraint Satisfaction Problem is either in Π₂^P, or PSpace-complete. Additionally, we build a constraint language on a 6-element domain such that the Quantified Constraint Satisfaction Problem over this language is Π₂^P-complete.

Discussions

• Quantified CSPs are either PSPACE-complete or inside Pi_2 [hn, 2 points, 0 comments]

Related

• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• Meditations on Quantified Constraint Satisfaction
• Low-level dichotomy for Quantified Constraint Satisfaction Problems
• Generalizing Consistency and other Constraint Properties to Quantified Constraints
• Tractability Frontier for Dually-Closed Temporal Quantified Constraint Satisfaction Problems