## On searching for small Kochen-Specker vector systems (extended version)

*Felix Arends*, *Joël
Ouaknine*, and *Charles W. Wampler*
Kochen-Specker (KS) vector systems are sets of vectors in
**R**^{3} with the property that it is impossible to assign 0s
and 1s to the vectors in such a way that no two orthogonal vectors are
assigned 0 and no three mutually orthogonal vectors are assigned
1. The existence of such sets forms the basis of the Kochen-Specker
and Free Will theorems. Currently, the smallest known KS vector system
contains 31 vectors. In this paper, we establish a lower bound of 18
on the size of any KS vector system. This requires us to consider a
mix of graph-theoretic and topological embedding problems, which we
investigate both from theoretical and practical angles. We propose
several algorithms to tackle these problems and report on extensive
experiments. At the time of writing, a large gap remains between the
best lower and upper bounds for the minimum size of KS vector systems.

*Proceedings of WG 11*, LNCS 6986, 2011. 16 pages.

PDF
© 2011
Springer-Verlag.

Imprint / Data Protection