On definition of IP class

Question

I'm a little bit lost with the actual definition of IP, some sources define as interaction between algorithms starting with Verifier, another one does not any put restriction on who send the first message. This simple question turn things messy ahead, when take into account the number of messages on definition of IP(k). Does matter who start the interaction?

Answer 1

In the definition of class IP(k), the interaction always ends with prover’s message. Otherwise there is no use for the last message (why?).

The situation is different for the definitions of public-coin interactive proof systems (also known as Arthur-Merlin proof systems), where sending a message from the verifier to the prover is the only way for the verifier to generate a random bit string. In Babai [Bab85], AM(k) is defined by the verifier (or Arthur) sending the first message and MA(k) is defined by the prover (or Merlin) sending the first message.

[Bab85] László Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 421–429, May 1985. DOI: 10.1145/22145.22192.

Answer 2

The answers above addressed your concerns, but I wanted to add a complete description of the definition of the class IP and AM and MA here as well.

Interactive Algorithms

Terminology

We have a prover $P$, a verifier $V$, and they are talking about some problem with language $L$.

They are given a string $x$ that both can see, then $P$ is trying to convince $V$ that $x \in L$. To do this they send lots of messages back and forth. Then we call $\lt P, V\gt(x)$ the function returning $1$ if $V$ thinks that $x \in L$ ($P$ is telling the truth) and $0$ if $V$ thinks that $x \notin L$ ($P$ is lying).

$V$ is required to return $\lt P, V\gt(x)$ after a polynomial amount of time with respect to the size of $x$, so the entire interaction can only take this long.

If $V$ wants to use randomness then it can take probabilistic polynomial time with respect to the size of $x$ instead. It can also generate as many random bits as it wants at any time, and can do this multiple times at different times (so it doesn't need to just request them all at once). The prover does not know what these random bits are, in other words, they are private coins.

It's actually really important that $V$ uses randomness, because if they don't, $P$ can just predict how the entire conversation between them will go, and send that as one message instead, which is equivalent to just sending the entire proof across, which is boring.

$P$ has an infinite amount of memory and can do as many things as it wants (even solve the halting problem) in constant time. However, it is restricted in that it can only send a polynomial number of messages, each of which is polynomial in size, before the interaction is done because $V$ is required to run in polynomial time.

If we create some algorithm (you could also think of it as a protocol) for describing what messages $V$ and $P$ send to each other given input $x$ and describing what they do about those messages and what $\lt P, V\gt(x)$ returns at the end, we call this algorithm an Interactive Algorithm. (with respect to the language $L$ that they are talking about)

Proof Systems

We can technically define an interactive algorithm in three parts: The protocol, the prover's algorithm, and the verifier's algorithm (which includes returning $\lt P, V\gt(x)$).

We will assume that all protocols are essentially equivalent. We can do this partially because, if $P$ or $V$ sent two messages in a row, it is the equivalent of one message. So the interaction will always be a message from one to the other and then a response back and a response from that and etc. Also, we may assume that $P$ always sends the last message, since if $V$ sent the last message it wouldn't be adding any new information it needed to know before returning $\lt P, V\gt(x)$. So the only thing that's really relevant is who sends the first message, and how the messages are interpreted by the other person. The second one isn't important because we assume they are using a "reasonable encoding" like in other places of TCS. The first one doesn't matter with all of $IP$ because, given $n$ rounds, $n+1$ rounds is equivalent to either the prover or the verifier going first with $n$ rounds.

Now we denote an interactive algorithm with prover algorithm $P$ and verifier algorithm $V$ as $(P, V)$.

This notation may seem different than the above section, but it's just a way of describing a prover's behaviour and verifier's behaviour, which is essentially what we were talking about above anyway, just in an more informal way.

Given some $(V, P)$, note that we could create another $P*$ that, from $V$'s perspective, seems to follow the protocol but actually returns the wrong results. Then we could simply call this new algorithm $(V, P^*)$. It would be dumb but it is something we could do.

Now, we call $(V, P)$ (under some language $L$) a Proof System if it satisfies the following conditions:

• If $x \in L$, then $\text{Pr}[\lt P, V\gt(x)=1]=1$
• If $x \notin L$, then for any possible $P^*$ we have $\text{Pr}[\lt P, V\gt(x)=1]\leq\frac{1}{2}$

$IP$

A language $L$ is in the class $IP$ (interactive proofs) if there exists some proof system in $L$.

Our verifier $V$ above was described as using private coins, in other words, coins that the prover $P$ does not know the value of. This is what differentiates $IP$ from $MA$ and $AM$ and etc. - those other complexity classes use public coins where the result of a coin flip is known to $V$ and $P$.

$IP[n]$

A language $L$ is in the class $IP[n]$ if there exists some proof system in $L$ that uses only $n$ rounds of communication (where each message sent by $V$ counts as one round and each message sent by $P$ also counts as one round, so for example a message sent from $V$ to $P$ and a response message sent from $P$ to $V$ counts as two rounds). Like before, any protocol is valid, as long as it only has $n$ rounds of communication.

Note that $n$ must be polynomial because we are still restricted to $V$ running in polynomial time relative to the size of the input $x$.

Arthur Merlin

Terminology

This has a prover $P$ and verifier $V$ that function in exactly the way as described in the introduction section above, except that when random coins are generated, they are visible to $P$ and $V$. This is called a public coin system, as opposed to the private coin system above. Note though that, like before, $V$ can generate coins whenever they are needed, and then the important part here is that $P$ doesn't know the value of those coins before $V$ can read what they are as well, so $P$ can't see into the future and determine what the value of the coins will be before they are flipped, but once they are generated $P$ can see them at the same time as $V$ (so they aren't private to $V$).

$V$ is required to be deterministic, with the exception that the only piece of randomness it's algorithm has is the value of the coins it generates. In other words, if the coins return the same values twice, $V$ is expected to have the same behavior each time.

$P$ will be restricted to only sending one message.

Like before, they are working under some language $L$, and given some string $x$ that they can both see, $P$ is trying to convince $V$ that $x \in L$. We will call $\pi$ the the "proof" sent by the prover, since the prover only sends one message. We will also call $r$ the set of all the values of the random coins generated by $V$ in a single interaction ($P$ and $V$ sending one message and then $V$ returning if it thinks $x\in L$ or not), and remember that $P$ and $V$ can both see these coins once their values are generated. $r$ can have different values every time this interaction between $V$ and $P$ occurs, because they are random coins.

Now we will define $V(x, \pi, r)$ as the function similar to $\lt P, V\gt(x)$ above, where $V(x, \pi, r)$ returns $1$ if $V$ believes that $x \in L$ ($V$ thinks $P$ is telling the truth), and $V(x, \pi, r)$ returns $0$ if $V$ believes that $x \notin L$ ($V$ thinks that $P$ is lying). This is dependent on the input $x$, the message $\pi$ sent by $P$, and the random coins $r$ generated by $V$, as expected.

AM

Consider the case where the verifier $V$ (King Authur) sends only it's random coins to the prover $P$ (Merlin), and may not generate any random coins after that. Then $P$ sends a message (it's "proof" $\pi$) back, and $V$ then examines this message (deterministically) and returns $V(x, \pi, r)$.

A language $L$ is in the class $AM$ if has a protocol in this manner such that

• If $x \in L$, then for all possible $r$ there exists a $r$ such that $V(x, \pi, r)=1$
• If $x \notin L$, then these exists $\pi$ such that for all possible $r$, $\text{Pr}[V(x, \pi, r)=1]\leq\frac{1}{2}$

MA

In this case, the prover simply sends it's proof $\pi$ to $V$, and then $V$ examines this message, generating random coins as desired, and then returns $V(x, \pi, r)$.

A language $L$ is in the class $MA$ if has a protocol in this manner such that

• If $x \in L$, then there exists $\pi$ such that for all possible $r$ we have $V(x, \pi, r)=1$
• If $x \notin L$, then for all $\pi$ that could be sent by $P$, we have $\text{Pr}[V(x, \pi, r)=1]\leq\frac{1}{2}$

Much of this is from here.

Answer 3

In fact does not matter (the classes of recognized languages are the same) as can be seen here:Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, László Babai