What is it about?
This article studies a class of computational problems, called Quantified Constraint Satisfaction Problems (QCSPs), that are used in Artificial Intelligence to model non-monotonic reasoning. The principal concern is how complicated these problems are for a computer to solve, because we know some of them can be solved efficiently, while we strongly suspect that others cannot. Typically, efficiently means in time polynomial in the size of the input. For us, it is something different, something broader, and something that is more often associated with hardness. NP is the class of problems whose yes-instances can be verified in polynomial time. For us, it is the "easy" class. Co-NP is the class of problems whose no-instances can be verified in polynomial time. For us, it will be the hard class.
Featured Image
Photo by Wim van 't Einde on Unsplash
Why is it important?
The interface between logic and algebra provides a home for some beautiful mathematics. Our principal result is that the class of QCSPs, in a particular algebraic formulation, contains problems all of which are in NP or at least as hard as the hardest problems in Co-NP. Well, this is not so beautiful, yet! The beauty is that the borderline between these different levels of difficulty is specified by properties of an algebra associated with the set of relations available in the corresponding QCSP. The latter is called the constraint language - a logical object - and the former its clone of polymorphisms - an algebraic object. When one considers direct powers of the polymorphism clone, one can consider minimal generating sets for these direct powers. In some cases, these sets are known to be of polynomial size, and in other cases they are known to be of exponential size. This was an outstanding result of the last author in another paper (Zhuk [2019]). What we show in this paper is that the polynomial generating sets correspond to QCSPs that are in NP and the exponential generating sets correspond to QCSPs that are at least as hard as the hardest problems in Co-NP.
Perspectives
Since Zhuk and Martin [2017] showed that the usual formulation of the QCSP does not divide its complexity according to the size of the generating set of powers of the polymorphism clone, by showing an example with exponential growth but a QCSP solvable in polynomial time, the unusual formulation of this paper takes on a new significance. Indeed, what is the correct formulation? Any formulation that gives beautiful mathematics must be justifiable! The beauty behind the normal formulation of the QCSP is still hidden from us at this juncture.
Catarina Carvalho
University of Hertfordshire
Read the Original
This page is a summary of: The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation, ACM Transactions on Computational Logic, January 2023, ACM (Association for Computing Machinery),
DOI: 10.1145/3568397.
You can read the full text:
Contributors
The following have contributed to this page
