Classical, quantum and nonsignalling resources in bipartite games (Q387029)

The paper studies bipartite games that arise in the context of nonlocality with the help of graph theory. The main results show that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games admit a nonsignalling winning strategy is in P. The authors discuss relations between quantum winning strategies and orthogonality graphs. They also show that every pseudotelepathy game (a forbidden-edge game is called a pseudotelepathy game if Alice and Bob have a winning strategy using shared entanglement) yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof system that is classically sound, but that becomes unsound when provers use shared entanglement.