Chen Conjecture for quantified constraint satisfaction problems
Statement
Let be a finite constraint language with all constants. Its polymorphism clone has the polynomially generated powers (PGP) property if, for some polynomial , every power has a generating subset of size at most under , where is the domain of . Chen Conjecture. If has PGP, then is in NP; otherwise is PSpace-complete. This conjecture proposes a dichotomy for the complexity of quantified constraint satisfaction problems: the PGP case admits an NP upper bound, while failure of PGP should force PSpace-completeness. It is identified in the source as the outstanding conjecture in the area; its resolution status is not specified here.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.