The complete classification for quantified equality constraints

DOI10.1137/1.9781611977554.CH103MaRDI QIDQ6364329zbMATH OpenOpenAlexFDO

Authors D. N. Zhuk, Barnaby Martin, Michał Wrona

Publication date 1 April 2021

Full work available at URL https://doi.org/10.1137/1.9781611977554.ch103

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: We prove that QCSP$(mathbbN;x=yightarrowy=z)$ is PSpace-complete, settling a question open for more than ten years. This completes the complexity classification for the QCSP over equality languages as a trichotomy between Logspace, NP-complete and PSpace-complete. We additionally settle the classification for bounded alternation QCSP$(Gamma)$, for $Gamma$ an equality language. Such problems are either in Logspace, NP-complete, co-NP-complete or rise in complexity in the Polynomial Hierarchy.

Cited in

(3)

• On classifying continuous constraint satisfaction problems
• Identifying tractable quantified temporal constraints within Ord-Horn
• The school of V. B. Kudryavtsev at the chair of mathematical theory of intelligent systems: traditions and development

This page was built for publication: The complete classification for quantified equality constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6364329)