2013-10-24 Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics
Jeudi 24 octobre, 11h30, salle de séminaires, LIRMM
Titre :Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics
par Georg Gottlob (Univ. Oxford)
Motivated by considerations in quantum mechanics, we introduce the class of robust constraint satisfaction
problems in which the question is whether every partial assignment of a certain length can be extended to a
solution, provided the partial assignment does not violate any of the constraints of the given instance.
We explore the complexity of specific robust colorability and robust satisfiability problems, and show that they are NP-complete. We then use these results to establish the computational intractability of detecting local hidden-variable models in quantum mechanics.
A paper on these results has been published at IJCAI 2013. We also report about a more recent result about the complexity of detecting hidden variables in possibilistic models with two experimenters and Boolean outcomes. In fact, this problem is not only tractable, but is actually in first order (FO), and thus decidable in AC_0.
Last update on 10/02/2014