../

2026-10-19 TOC Scribe

$\newcommand{\BPP}{\mathbf{BPP}}$ $\newcommand{\NP}{\mathbf{NP}}$ $\newcommand{\IP}{\mathbf{IP}}$ $\newcommand{\dip}{\mathbf{dIP}}$ $\newcommand{\pspace}{\mathbf{PSPACE}}$ $\newcommand{\BS}{\{0, 1\}}$

TOC

  • $\BPP$-hardness
  • Interactive Proofs, $\dip$
  • $\IP[k]$
  • Graph Non-Isomorphism
  • $\IP \subseteq \pspace$
  • Arthur-Merlin, $\mathbf{AM}$
  • Set Lower-Bound

Recap

Recall that we have completed our discussion on Randomized classes ($\BPP, \mathbf{RP}$, etc.). There are still many open question in this domain.

  • Is there a hierarchy theorem for $\BPP$?
    • We have hierarchy for both time and space
  • Are there complete problems for $\BPP$?

Why no complete problems for $\BPP$?

We usually define the check of completeness in terms of TMs because, well, the problems are TM and it’s very easy to check them using TMs too. But the check here is more complicated.

DOUBT

$$ \{ \langle M, x, 1^n \rangle: \Pr[M(x; r) = 1 \ge 2/3] \} $$

This is the language of checking a $\BPP$. It is not clear how one would implement this using a TM. Positive instances are clearly easy to check by just counting. But how would one calculate the probability of negative instances?

We believe that this language is not in $\BPP$. This may be why we don’t have $\BPP$ hardness.

Interactive Proofs

Definition 1: Interactive Proof Protocol

Proof protocol involves a poly-time TM V that outputs a string and a function $p:\BS^*\rightarrow\BS^*$ such that the following interaction takes place

Notice the asymmetry in terms of computational power in $V$ and $p$. $p$ is any function. It may even be uncomputable. $V$ is a deterministic poly-time TM.

This is intentional. We want the verifier to be efficient and we want the prover to have unlimited power. If our system is sound and complete under this then it would be so under a weaker prover as well.

Definition 2: Class $\dip$

A language $L\in\dip$ if $\exists$ a poly-time TM V s.t

  • Complete
    • $x\in L \implies \exists$ some function $p$ such that $\text{Out}_V = 1$
    • $x\notin L \implies \forall$ functions $p$ $\text{Out}_V = 0$

$\dip[k]$ indicates that the proof has $k$ rounds. When we just mention $\dip$ it actually means $\dip = \bigcup_{c > 1} \dip[n^c]$

Relation with $\NP$

$$\dip = \NP$$

This means that interactivity adds nothing. We know that $\NP$ kinda resembles a non-interactive proof with the witness being the proof. Deterministic interactive proofs are no more powerful that non-interactive proofs.

This also have the implication that $\dip[2] = \dip$ where the communication is just the witness string of $\NP$.

Random Interactive Proofs

TODO