The complexity of the Quantified CSP having the polynomially generated powers property

arXiv2110.09504MaRDI QIDQ6380685FDOQ6380685

Authors: D. N. Zhuk 

Publication date: 18 October 2021

Abstract: It is known that if an algebra of polymorphisms of the constraint language has the Polynomially Generated Powers (PGP) Property then the Quantified CSP can be reduced to the CSP over the same constraint language with constants. The only limitation of this reduction is that it is applicable only for the constraint languages with constants. We drastically simplified the reduction and generalized it for constraint languages without constants. As a result, we completely classified the complexity of the QCSP for constraint languages having the PGP property.

This page was built for publication: The complexity of the Quantified CSP having the polynomially generated powers property

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