QCSP Monsters and the Demise of the Chen Conjecture

DOI10.1145/3563820MaRDI QIDQ5889780zbMATH OpenOpenAlexWikidataFDO

Authors D. N. Zhuk, Barnaby Martin

Publication date 27 April 2023

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3563820

zbMATH Keywords

computational complexityconstraint satisfaction problemCSP dichotomyquantified constraintsrelational clonesweak near-unanimity

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• QCSP monsters and the demise of the chen conjecture
• Quantified constraint satisfaction and the polynomially generated powers property
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• The complexity of quantified constraints using the algebraic formulation
• STACS 2005

Cited in

(6)

• QCSP monsters and the demise of the chen conjecture
• Generalisations of matrix partitions: complexity and obstructions
• Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
• Identifying tractable quantified temporal constraints within Ord-Horn
• _2P vs PSpace dichotomy for the quantified constraint satisfaction problem
• The school of V. B. Kudryavtsev at the chair of mathematical theory of intelligent systems: traditions and development

This page was built for publication: QCSP Monsters and the Demise of the Chen Conjecture

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