ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let L\mathcal{L} be the class of binary constraint system games, and let SAT⁡matrix(L)\operatorname{SAT}_{matrix}(\mathcal{L}) and SAT⁡RU(L)\operatorname{SAT}_{\mathcal{R}^{\mathcal{U}}}(\mathcal{L}) denote the corresponding satisfiability problems for finite-dimensional matrix strategies and universal tracial strategies, respectively. The complexity classes RE\mathrm{RE} and Π20\Pi^0_2 are the recursively enumerable and second-level arithmetical hierarchy classes.

Completeness conjecture. In parts (a) and (b) of the cited dichotomy theorem, SAT⁡matrix(L)\operatorname{SAT}_{matrix}(\mathcal{L}) is RE\mathrm{RE}-complete, and SAT⁡RU(L)\operatorname{SAT}_{\mathcal{R}^{\mathcal{U}}}(\mathcal{L}) is Π20\Pi^0_2-complete.

The preceding results establish undecidability and the relevant lower bounds, while the MIP*=RE theorem and subsequent work establish the corresponding completeness results for arbitrary binary constraint systems. The conjecture asserts that these upper and lower bounds are also tight for the class L\mathcal{L} considered 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 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.