2
$\begingroup$

I was self-studying Interactive Protocols from Introduction to Computational Complexity by Arora, Barak. Initially, we define when we say a language $L \subset \{ 0,1 \}^*$ is a k round deterministic interactive proof system. In the definition, it appears $k$ is a constant and thus does not depend on the $|x|$ for any $x \in L$. Then we define dIP as the class of Languages having $k(n)$ rounds deterministic interactive proof system. I am confused as to what the parameter $n$ is? Ideally, it should be $|x|$ for every input $x \in L$. Perhaps this question is silly; if possible, please clear up my confusion.

$\endgroup$

1 Answer 1

3
$\begingroup$

This seems to be an oversight. I assume you're referring to the old draft available online of Computational Complexity: A Modern Approach by Arora and Barak, which gives an incomplete definition of dIP (Section 8.1) (and also IP). It might have been fixed in the published version of the book (I don't have access to it).

$k$ in the definition of "k-round (deterministic) interactive proof system" should be a function (similarly, the later definition of IP does introduce $k$ as a function $k : \mathbb{N} \to \mathbb{N}$, but that definition is also incomplete because it does not use $k$).

First, the number of rounds should be made apparent in the definition of the "out" function which evaluates the result of $k$ rounds of interaction. Here $k$ is a constant, $k \in \mathbb{N}$.

The output of $f$ at the end of $k$ rounds of interaction, denoted $\mathrm{out}_f^k\langle f,g\rangle(x)$, is defined to be $f(x,a_1,\dots,a_k)$.

Then, the definition of deterministic interactive proof systems should be parameterized by a function. It will appear as an index of $\mathrm{out}$.

Let $k : \mathbb{N} \to \mathbb{N}$. A language $L$ has a $k$-round deterministic interactive proof system if there is a deterministic TM $V$ that, on input $x,a_1,\dots,a_i$, runs in time polynomial in $|x|$, satisfying

  • Completeness: $x\in L \implies \exists P : \{0,1\}^\star \to \{0,1\}^\star, \mathrm{out}_V^{k(|x|)}\langle V,P\rangle(x) = 1$
  • Soundness: $x\not\in L \implies \forall P : \{0,1\}^\star \to \{0,1\}^\star, \mathrm{out}_V^{k(|x|)}\langle V,P\rangle(x) = 0$

The class $\mathbf{dIP}$ contains all languages with a $p$-round deterministic interactive proof system for some polynomial $p$.

$\endgroup$
1
  • $\begingroup$ Yes, I was referring to the old draft; there seems to be a lot of errata in it. Thanks for clearing up my confusion. $\endgroup$ Commented Jul 12 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.