Completeness conjecture for matrix and universal tracial satisfiability
Statement
Let be the class of binary constraint system games, and let and denote the corresponding satisfiability problems for finite-dimensional matrix strategies and universal tracial strategies, respectively. The complexity classes and are the recursively enumerable and second-level arithmetical hierarchy classes.
Completeness conjecture. In parts (a) and (b) of the cited dichotomy theorem, is -complete, and is -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 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.