Classical, quantum and nonsignalling resources in bipartite games (Q387029): Difference between revisions

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.