The mighty tuple II conjecture for quantified constraint satisfaction
Statement
Let be a finite domain, let be a constraint language on , and let denote the quantified constraint satisfaction problem for . A mighty tuple II is the structural configuration defined in the paper, and a constraint language q-defines such a tuple when it can define it by quantified primitive-positive formulas. Mighty tuple II conjecture. is PSpace-complete if and only if q-defines a mighty tuple II. The paper establishes related implications among mighty tuples and proves classifications in some restricted settings, but the converse implication from a mighty tuple I to a mighty tuple II is not known in general; this conjecture proposes the corresponding PSpace-completeness dichotomy.
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.