Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-187 | 7th August 2013 21:46

Interactive proofs with competing teams of no-signaling provers

RSS-Feed




Revision #2
Authors: Gus Gutoski
Accepted on: 7th August 2013 21:46
Downloads: 1345
Keywords: 


Abstract:

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses.

We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof:

1. Two-turn multi-prover interactive proofs with only one team of no-signaling provers.

2. Two-turn competing-prover interactive proofs with only one prover per team.

Our result implies that the complexity of these two models is unchanged by the addition of a second competing team of no-signaling provers in the first case and by the addition of a second no-signaling prover to each team in the second case. Moreover, our result unifies and subsumes prior PSPACE upper bounds on these classes.



Changes to previous version:

Final version. Published in the Chicago Journal of Theoretical Computer Science, article 7, 2013.


Revision #1 to TR10-187 | 15th October 2011 05:49

Interactive proofs with competing teams of no-signaling provers





Revision #1
Authors: Gus Gutoski
Accepted on: 15th October 2011 05:49
Downloads: 1443
Keywords: 


Abstract:

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses.

We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof:

1. Two-turn multi-prover interactive proofs with only one team of no-signaling provers.

2. Two-turn competing-prover interactive proofs with only one prover per team.

Our result implies that the complexity of these two models is unchanged by the addition of a second competing team of no-signaling provers in the first case and by the addition of a second no-signaling prover to each team in the second case. Moreover, our result unifies and subsumes prior PSPACE upper bounds on these classes.



Changes to previous version:

minor revisions, mostly to the introduction.


Paper:

TR10-187 | 3rd December 2010 20:41

Interactive proofs with competing teams of no-signaling provers





TR10-187
Authors: Gus Gutoski
Publication: 3rd December 2010 20:46
Downloads: 1702
Keywords: 


Abstract:

This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses.

We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof:

1. Two-turn multi-prover interactive proofs with only one team of no-signaling provers.

2. Two-turn competing-prover interactive proofs with only one prover per team.

Our result implies that the complexity of these two models is unchanged by the addition of a second competing team of no-signaling provers in the first case and by the addition of a second no-signaling prover to each team in the second case. Moreover, our result unifies and subsumes prior PSPACE upper bounds on these classes.



ISSN 1433-8092 | Imprint