Suggest edit — SU-CS254 FEB242025

Title

Name

Note

---
title: "SU-CS254 FEB242025"
source: https://www.jemoka.com/posts/kbhsu_cs254_feb242025/
date: 2025-02-24
---

Key Sequence Notation New Concepts Interactive Proof IP(k) Important Results / Claims An Anthropomorphic View of NP Graph Isomorphism is in NP IP = PSACE Questions Interesting Factoids An Anthropomorphic View of NP For some string \(x\), and language \(L\). We wonder:
\begin{equation} x \in^{?} L \end{equation}
We can consider NP as a two party game, whereby:
prover: looks at \(x, L\), and sends some proof \(w\) for \(x \in L\) verifier: does some polytime computation, and either accepts or rejects We want to make sure that this system follows the following patterns:
\(x \in L \implies \exists y \text{ s.t. } V\qty(x,y)\) accepts \(x \not \in L \implies \forall y, V\qty(x,y)\) rejects In general, think of the prover as actively malicious, in that it will try to convince you \(x \in L, \forall x\)
Interactive Proofs What happens if you allow the prover and verifier to interact? This is of course a larger class than NP, but is it strictly larger?
Suppose the prover and verifier could interact?
Interactive See Interactive Proof