Output details

Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics

<11>

This paper establishes striking connections between foundational questions in quantum mechanics, constraint satisfaction and complexity. A natural algorithmic question arising from quantum mechanics, of the complexity of determining whether the support of a probability model has a hidden-variable explanation, leads to a novel refinement of the constraint satisfaction paradigm, to robust constraint satisfaction, asking whether any partial solution of a given length can be extended to a full solution.

The precise tractability boundary is established for specific robust colorability and satisfiability problems. These are used to show the intractability of the hidden-variable problem for quantum mechanics.