Back to Search
Start Over
Classical, quantum and nonsignalling resources in bipartite games
- Source :
- Theoretical Computer Science. 486:61-72
- Publication Year :
- 2013
- Publisher :
- Elsevier BV, 2013.
-
Abstract
- We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are alternate proofs 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. We discuss relations between quantum winning strategies and orthogonality graphs. We also show that every pseudotelepathy game 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.
- Subjects :
- Discrete mathematics
Computer Science::Computer Science and Game Theory
General Computer Science
Orthogonality (programming)
Interactive proof system
Context (language use)
Graph theory
0102 computer and information sciences
Quantum entanglement
Mathematical proof
01 natural sciences
Theoretical Computer Science
Quantum nonlocality
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
0103 physical sciences
Bipartite graph
010306 general physics
Mathematical economics
Mathematics
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 486
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi...........86659934ec199384be6e6aaed924e3f9