We solve the problem of whether a set of quantum tests reveals state-independent contextuality and use this result to identify the simplest set of the minimal dimension. We also show that identifying state-independent contextuality graphs [R. Ramanat
han and P. Horodecki, Phys. Rev. Lett. 112, 040404 (2014)] is not sufficient for revealing state-independent contextuality.
Contextuality is a natural generalization of nonlocality which does not need composite systems or spacelike separation and offers a wider spectrum of interesting phenomena. Most notably, in quantum mechanics there exist scenarios where the contextual
behavior is independent of the quantum state. We show that the quest for an optimal inequality separating quantum from classical noncontextual correlations in an state-independent manner admits an exact solution, as it can be formulated as a linear program. We introduce the noncontextuality polytope as a generalization of the locality polytope, and apply our method to identify two different tight optimal inequalities for the most fundamental quantum scenario with state-independent contextuality.
