Skip to main content
deleted 2 characters in body; edited tags; edited title
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Clarification on the paper On The Power Why is there only a polynomial number of Multiprovers in multi-prover Interactive Protocols by Fortnow, Rompel, Sipserinteractive protocols?

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following: 1. There are provers $P_1, P_2, ..., P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers. 2. In one round a verifier can interact with more than one prover.

  1. There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
  2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Clarification on the paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following: 1. There are provers $P_1, P_2, ..., P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers. 2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Why is there only a polynomial number of provers in multi-prover interactive protocols?

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following:

  1. There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers.
  2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

added 1 character in body; edited title
Source Link

Clarification on the paper On The Power of Multi-prover interactive protocolsInteractive Protocols by Fortnow, Rompel, Sipser

The paper On The Power of MultMulti-prover interactive protocolsInteractive Protocols by Fortnow, Rompel, Sipser states the following: 1. There are provers $P_1, P_2, ..., P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers. 2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Clarification on the paper On The Power of Multi-prover interactive protocols by Fortnow, Rompel, Sipser

The paper On The Power of Mult-prover interactive protocols by Fortnow, Rompel, Sipser states the following: 1. There are provers $P_1, P_2, ..., P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers. 2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Clarification on the paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following: 1. There are provers $P_1, P_2, ..., P_k$ in a multi-prover interactive proof system such that $k$ is polynomial in the size of the input. The value of $k$ cannot exceed a polynomial because this would prevent the verifier in the system from accessing all the provers. 2. In one round a verifier can interact with more than one prover.

Since a verifier can interact with more than one prover in one round, is the real reason that the number of provers must be polynomial due to the fact that the total length of the messages to all the provers in one round must be polynomial in the length of the input?

Tweeted twitter.com/#!/StackCompSci/status/488469576188194816
edited title
Link

Clarification on the paper On The Power of MultMulti-prover interactive protocols by Fortnow, Rompel, Sipser

added 2 characters in body
Source Link
Loading
Source Link
Loading