Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras

Anuj Dawar, Nihil Shah

The Kochen-Specker no-go theorem established that hidden-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the par…