ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let AA be a finite domain, let Γ\Gamma be a constraint language on AA, and let \QCSP(Γ)\QCSP(\Gamma) denote the quantified constraint satisfaction problem for Γ\Gamma. 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. \QCSP(Γ)\QCSP(\Gamma) is PSpace-complete if and only if Γ\Gamma 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.