Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 440-445.
Abstract
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.
@inproceedings{ijcai2013p73,
title = {Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics},
author = {Abramsky, Samson and Gottlob, Georg and Kolaitis, Phokion G.},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {440--445},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/73},
}
TY - CPAPER TI - Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics AU - Abramsky, Samson AU - Gottlob, Georg AU - Kolaitis, Phokion G. T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 440 EP - 445 UR - https://ijcai.org/proceedings/2013/73 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
