BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Talks.cam//talks.cam.ac.uk// X-WR-CALNAME:Talks.cam BEGIN:VEVENT SUMMARY:Complexity of Satisfiability in Kochen-Specker Partial Boolean Alg ebras - Nihil Shah (University of Cambridge) DTSTART:20260320T140000Z DTEND:20260320T150000Z UID:TALK246703@talks.cam.ac.uk CONTACT:Ioannis Markakis DESCRIPTION:

The Kochen-Specker no-go theorem established that hidd en-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the partial Boolean algebra s tructure of projectors on a Hilbert space. Each partial Boolean algebra pr ovides a semantics for interpreting propositional logic. In this paper\, w e examine the complexity of propositional satisfiablity for various classe s of partial Boolean algebras. We first show that the satisfiability probl em for the class of non-trivial partial Boolean algebras is NP-complete. N ext\, we consider the satisfiability problem for the class of partial Bool ean algebras arising from projectors on finite dimensional Hilbert spaces. For real Hilbert spaces of dimension greater 2 and any complex Hilbert sp aces of dimension greater than 3\, we demonstrate that the satisfiablity p roblem is complete for the existential theory of the reals. Interestingly\ , the proofs of these results make use of Kochen-Specker sets as gadgets. As a corollary\, we conclude that deciding quantum homomorphism in these f ixed dimensions are also complete for the existential theory of the reals. Finally\, we show that the satisfiability problems for the class of all H ilbert spaces and all finite-dimensional Hilbert spaces is undecidable.

LOCATION:SS03\, Computer Laboratory END:VEVENT END:VCALENDAR