# Tag Info

Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals. Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. Prover chooses a color in $\{1,2,3,4\}$ for each of the following: Variable literals $V(x_i), V(\lnot x_i)$ ($2n$ colors in total). ...