Mathematics of the impossible, Chapter 11, Proofs

Thoughts 2023-05-11

The notion of proof is pervasive. We have seen many proofs in this book until now. But the notion extends to others realms of knowledge, including empirical science, law, and more. Complexity theory has contributed a great deal to the notion of proof, with important applications in several areas such as cryptography.

11.1 Static proofs

As remarked in section 5.1.0.1, we can think of problems in $\text {NP}$ as those admitting a solution that can be verified efficiently, namely in $\text {P}$ . Let us repeat the definition of $\text {NP}$ using the suggestive letter $V$ for verifier.

Definition 11.1. A function $f:X\subseteq \{0,1\}^* \to \{0,1\}$ is in $\text {NP}$ iff there is $V\in \text {P}$ (called “verifier”) and $d\in \mathbb {N}$ s.t.:

$\begin{aligned} f(x)=1\Leftrightarrow \exists y\in \{0,1\} ^{|x|^{d}}:V(x,y)=1. \end{aligned}$

We are naturally interested in fast proof verification, and especially the complexity of $V$ . It turns out that proofs can be encoded in a format that allows for very efficient verification. This message is already in the following.

Theorem 11.1. For any input length $n$ , $V$ in Definition 11.1 can be taken to be a 3CNF of size $n^{d}$ .

That is, whereas when defining $\text {NP}$ as a proof system we considered arbitrary verifiers $V$ in P, in fact the definition is unchanged if one selects a very restricted class of verifiers: small 3CNFs.

Proof. This is just a restatement of Theorem 5.1. QED

This extreme reduction in the verifier’s complexity is possible because we are allowing proofs to be long, longer than the original verifier’s running time. If we don’t allow for that, such a reduction is not known. Such “bounded proofs” are very interesting to study, but we shall not do so now.

Instead, we ask for more. The 3CNF in the above theorem still depends on the entire proof. We can ask for a verifier that only depends on few bits of the proof. Taking this to the extreme, we can ask whether $V$ can only read a constant number of bits from $y$ . Without randomness, this is impossible.

Exercise 11.1. Suppose $V$ in Definition 11.1 only reads $\le d$ bits of $y$ , for a constant $d$ . Show that the corresponding class would be the same as P.

Surprisingly, if we allow randomness this is possible. Moreover, the use of randomness is fairly limited – only logarithmically many bits – yielding the following central characterization.

Theorem 11.2. A function $f:X\subseteq \{0,1\}^* \to \{0,1\}$ is in $\text {NP}$ iff there is $V\in \text {P}$ and $d\in \mathbb {N}$ s.t.:

$f(x)=1\Rightarrow \exists y\in \{0,1\} ^{|x|^{d}}:\mathbb {P}_{r\in \{0,1\} ^{d\log |x|}}[V(x,y,r)=1]=1$ ,

$f(x)=0\Rightarrow \forall y\in \{0,1\} ^{|x|^{d}}:\mathbb {P}_{r\in \{0,1\} ^{d\log |x|}}[V(x,y,r)=1]<0.01$ ,

and moreover $V$ reads $\le d$ bits of $y$ .

Exercise 11.2. Prove the “only if” in Theorem 11.2 in the specific case $f=0.01\text {-Gap-3Sat}$ .

Given this exercise, the “only if” direction for any problem in NP follows from the advanced result that any problem in NP can be map reduced to $0.01$ -Gap-3Sat (which is essentially Theorem 4.7, except we did not claim map reductions or a specific constant there).

Exercise 11.3. Prove the “if” in Theorem 11.2.

11.2 Zero-knowledge

In Theorem 11.2 the verifier gains “constant confidence” about the validity of the proof, just be inspecting a constant number of bits. Hence the verifier “learns” at most a constant number of bits of the proof. This is remarkable, but we can further ask if we can modify the proof so that the verifier “learns nothing” about the proof. Such proofs are called zero knowledge and are extensively studied and applied.

We sketch how this is done for Gap-3Color, which is also NP-complete. Rather than a single proof $y$ , now the verifier will receive a random proof $Y$ . This $Y$ is obtained from a 3 coloring $y$ by randomly permuting colors (so for any $y$ the corresponding $Y$ is uniform over 6 colorings). The verifier will pick a random edge and inspect the corresponding endpoints, and accept if they are different.

The verifier learn nothing because all that they see is two random different color. One can formalize “learning nothing” by noting that the verifier can produce this distribution by themselves, without looking at the proof. (So why does the verifier gain anything from $y$ ? The fact that a proof $y$ has been written down means that colors have been picked so that every two endpoints are uniform colors, something that the verifier is not easily able to reproduce.)

This gives a zero-knowledge proof for verifiers that follow the protocol of just inspecting an edge. In a cryptographic setting one has to worry about verifiers which don’t follow the protocol. Using cryptographic assumptions, one can force the verifiers to follow the protocol by considering an interactive proof: First a proof $y$ is committed to but not revealed, then the verifier selects an edge to inspect, and only then the corresponding colors are revealed, and only those. This protocol lends itself to a physical implementation.

11.3 Interactive proofs

We now consider interactive proofs. Here the verifier $V$ engages in a protocol with a prover $P$ . Given an input $x$ to both $V$ and $P$ , the verifier asks questions, the prover replies, the verifier asks more questions, and so on. The case of NP corresponds to the prover simply sending $y$ to $V$ .

It turns out that it suffices for the verifier to send uniformly random strings $Q_{1},Q_{2},\ldots$ bits to $P$ . This leads to a simple definition.

Definition 11.2. A function $f:X\subseteq \{0,1\}^* \to \{0,1\}$ admits an efficient interactive proof, abbreviated IP, if there is $V\in \text {P}$ and $d\in \mathbb {N}$ such that for every $x\in \{0,1\} ^{n}$ , letting $b:=n^{d}$ :

If $f(x)=1$ then $\exists P:\{0,1\}^* \to \{0,1\} ^{b}$ such that
$\begin{aligned} V\left (P(Q_{1}),P(Q_{1},Q_{2}),\ldots ,P(Q_{1},Q_{2},\ldots ,Q_{b})\right )=1 \end{aligned}$

for every $Q_{1},Q_{2},\ldots ,Q_{b}\in \{0,1\} ^{b}$ .
If $f(x)=0$ then $\forall P:\{0,1\}^* \to \{0,1\} ^{b}$ we have
$\begin{aligned} \mathbb {P}_{Q_{1},Q_{2},\ldots ,Q_{b}\in \{0,1\} ^{b}}\left [V\left (P(Q_{1}),P(Q_{1},Q_{2}),\ldots ,P(Q_{1},Q_{2},\ldots ,Q_{b})\right )=1\right ]\le 1/3. \end{aligned}$

The following amazing result shows the power of interactive proofs, compared to non-interactive proofs. We can think of NP as “reading a book” and IP as “going to class and asking questions.” We don’t yet know how to replace teachers with books.

Theorem 11.3. [41, 58] $\text { IP}=\text {PSpace}$ .

In the rest of this section we present the main ideas in the proof of 11.3, establishing a weaker result. In particular we show that IP contains problems not known to be in NP.

Theorem 11.4. Given a field $\mathbb {F}$ , an arithmetic circuit $C(x_{1},x_{2},\ldots ,x_{v})$ over $\mathbb {F}$ computing a polynomial of degree $d$ , and an element $s\in \mathbb {F},$ deciding if

$\begin{aligned} \sum _{x_{1},x_{2},\ldots ,x_{v}\in \{0,1\} }C(x_{1},x_{2},\ldots ,x_{v})=s~~~~(11.1) \end{aligned}$

is in IP, whenever $(1-d/q)^{v}\ge 2/3$ .

Proof. If $v=1$ then $V$ can decide this question by itself, by evaluating the circuit. For larger $v$ we give a way to reduce $v$ by $1$ .

As the first prover answer, $V$ expects a polynomial $p$ of degree $d$ in the variable $x$ , which is meant to be

$\begin{aligned} s'(x):=\sum _{x_{2},x_{3},\ldots ,x_{n}\in \{0,1\} }C(x,x_{2},x_{3}\ldots ,x_{n}). \end{aligned}$

$V$ checks if $p(0)+p(1)=s$ , and if not rejects. Otherwise, it recursively runs the protocol to verify that

$\begin{aligned} \sum _{x_{2},x_{3},\ldots ,x_{n}\in \{0,1\} }C(Q_{1},x_{2},x_{3},\ldots ,x_{n})=p(Q_{1}).~~~~(11.2) \end{aligned}$

This concludes the description of the protocol. We now verify its correctness.

In case equation (??) is true, $P$ can send polynomials that cause $V$ to accept.

In case equation (??) is false, $s'(0)+s'(1)\ne s$ . Hence, unless $V$ rejects right away because $p(0)+p(1)\ne s$ , we have $p\ne s'$ . The polynomials $p$ and $s'$ have degree $\le d$ . Hence by Lemma 2.3

$\begin{aligned} \mathbb {P}_{Q_{1}}[p(Q_{1})\ne s'(Q_{1})]\ge 1-d/q. \end{aligned}$

When this event occurs, equation (??) is again false, and we can repeat the argument. Overall, the probability that we maintain a false statement throughout the protocol is $\ge (1-d/q)^{v}$ . QED

Corollary 11.1. Given a 3CNF formula $\phi$ and $k\in \mathbb {N}$ , deciding if $\phi$ has exactly $k$ satisfying assignments is in $\text {IP}$ .

The proof uses a far-reaching technique: arithmetization. We construct an arithmetic circuit $C_{\phi }$ over a field $\mathbb {F}$ which agrees with $\phi$ on boolean inputs, but that can then be evaluated over other elements of the field.

Exercise 11.4. Prove Corollary 11.1.

The study of interactive proofs is rich. Many aspects are of interest, including:

The efficiency of the prover (does it have to be unbounded, randomized, etc.), and of the verifier.
The number of rounds.
The tradeoff betwen the error and the other parameters.

References

[1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59–78. IEEE Computer Society, 2015.

[2] Leonard Adleman. Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), pages 75–83. 1978.

[3] Mikl�s Ajtai. $\Sigma \sp {1}\sb {1}$ -formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1–48, 1983.

[4] Mikl�s Ajtai. A non-linear time lower bound for boolean branching programs. Theory of Computing, 1(1):149–176, 2005.

[5] Eric Allender. A note on the power of threshold circuits. In 30th Symposium on Foundations of Computer Science, pages 580–584, Research Triangle Park, North Carolina, 30 October–1 November 1989. IEEE.

[6] Eric Allender. The division breakthroughs. Bulletin of the EATCS, 74:61–77, 2001.

[7] Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3), 2010.

[8] Noga Alon, Oded Goldreich, Johan H�stad, and Ren� Peralta. Simple constructions of almost $k$ -wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992.

[9] Dana Angluin and Leslie G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. Syst. Sci., 18(2):155–193, 1979.

[10] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. of the ACM, 45(3):501–555, May 1998.

[11] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087–1097, 2018.

[12] Kenneth E. Batcher. Sorting networks and their applications. In AFIPS Spring Joint Computing Conference, volume 32, pages 307–314, 1968.

[13] Paul Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM J. Comput., 15(4):994–1003, 1986.

[14] Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. of the ACM, 50(2):154–195, 2003.

[15] Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. on Computing, 21(1):54–58, 1992.

[16] Samuel R. Buss and Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. Comput. Complex., 24(3):533–600, 2015.

[17] Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits “just beyond” known lower bounds. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 34–41. ACM, 2019.

[18] Richard Cleve. Towards optimal simulations of formulas by bounded-width programs. Computational Complexity, 1:91–105, 1991.

[19] Stephen A. Cook. A hierarchy for nondeterministic time complexity. J. of Computer and System Sciences, 7(4):343–353, 1973.

[20] L. Csanky. Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976.

[21] Lance Fortnow. Time-space tradeoffs for satisfiability. J. Comput. Syst. Sci., 60(2):337–353, 2000.

[22] Aviezri S. Fraenkel and David Lichtenstein. Computing a perfect strategy for n x n chess requires time exponential in n. J. Comb. Theory, Ser. A, 31(2):199–214, 1981.

[23] Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In ACM Symp. on the Theory of Computing (STOC), pages 345–354, 1989.

[24] Anka Gajentaan and Mark H. Overmars. On a class of ${O}(n^2)$ problems in computational geometry. Comput. Geom., 5:165–185, 1995.

[25] M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.

[26] K. G�del. �ber formal unentscheidbare s�tze der Principia Mathematica und verwandter systeme I. Monatsh. Math. Phys., 38, 1931.

[27] Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[28] Raymond Greenlaw, H. James Hoover, and Walter Ruzzo. Limits to Parallel Computation: P-Completeness Theory. 02 2001.

[29] David Harvey and Joris van der Hoeven. Integer multiplication in time $O(n\mathrm {log}\, n)$ . Annals of Mathematics, 193(2):563 – 617, 2021.

[30] F. C. Hennie. One-tape, off-line turing machine computations. Information and Control, 8(6):553–578, 1965.

[31] Fred Hennie and Richard Stearns. Two-tape simulation of multitape turing machines. J. of the ACM, 13:533–546, October 1966.

[32] John E. Hopcroft, Wolfgang J. Paul, and Leslie G. Valiant. On time versus space. J. ACM, 24(2):332–337, 1977.

[33] Russell Impagliazzo and Ramamohan Paturi. The complexity of $k$ -sat. In IEEE Conf. on Computational Complexity (CCC), pages 237–, 1999.

[34] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997.

[35] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Computer & Systems Sciences, 63(4):512–530, Dec 2001.

[36] Russell Impagliazzo and Avi Wigderson. $\mathit {P} = \mathit {BPP}$ if $E$ requires exponential circuits: Derandomizing the XOR lemma. In 29th ACM Symp. on the Theory of Computing (STOC), pages 220–229. ACM, 1997.

[37] Richard M. Karp and Richard J. Lipton. Turing machines that take advice. L’Enseignement Math�matique. Revue Internationale. IIe S�rie, 28(3-4):191–209, 1982.

[38] Kojiro Kobayashi. On the structure of one-tape nondeterministic turing machine time hierarchy. Theor. Comput. Sci., 40:175–193, 1985.

[39] Kasper Green Larsen, Omri Weinstein, and Huacheng Yu. Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. SIAM J. Comput., 49(5), 2020.

[40] Leonid A. Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115–116, 1973.

[41] Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. J. of the ACM, 39(4):859–868, October 1992.

[42] O. B. Lupanov. A method of circuit synthesis. Izv. VUZ Radiofiz., 1:120–140, 1958.

[43] Wolfgang Maass and Amir Schorr. Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. on Computing, 16(1):195–202, 1987.

[44] David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC $^1$ . J. of Computer and System Sciences, 38(1):150–164, 1989.

[45] Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. on Computing, 22(4):838–856, 1993.

[46] E. I. Nechiporuk. A boolean function. Soviet Mathematics-Doklady, 169(4):765–766, 1966.

[47] Valery A. Nepomnjaščiĭ. Rudimentary predicates and Turing calculations. Soviet Mathematics-Doklady, 11(6):1462–1465, 1970.

[48] NEU. From RAM to SAT. Available at http://www.ccs.neu.edu/home/viola/, 2012.

[49] Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425–440, 1991.

[50] Wolfgang J. Paul, Nicholas Pippenger, Endre Szemer�di, and William T. Trotter. On determinism versus non-determinism and related problems (preliminary version). In IEEE Symp. on Foundations of Computer Science (FOCS), pages 429–438, 1983.

[51] Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. of the ACM, 26(2):361–381, 1979.

[52] Alexander Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akademiya Nauk SSSR. Matematicheskie Zametki, 41(4):598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.

[53] Omer Reingold. Undirected connectivity in log-space. J. of the ACM, 55(4), 2008.

[54] J. M. Robson. N by N checkers is exptime complete. SIAM J. Comput., 13(2):252–267, 1984.

[55] Rahul Santhanam. On separators, segregators and time versus space. In IEEE Conf. on Computational Complexity (CCC), pages 286–294, 2001.

[56] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970.

[57] Arnold Sch�nhage. Storage modification machines. SIAM J. Comput., 9(3):490–508, 1980.

[58] Adi Shamir. IP = PSPACE. J. of the ACM, 39(4):869–877, October 1992.

[59] Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System Tech. J., 28:59–98, 1949.

[60] Victor Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189):435–447, 1990.

[61] Alan Siegel. On universal classes of extremely random constant-time hash functions. SIAM J. on Computing, 33(3):505–543, 2004.

[62] Michael Sipser. A complexity theoretic approach to randomness. In ACM Symp. on the Theory of Computing (STOC), pages 330–335, 1983.

[63] Roman Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In 19th ACM Symp. on the Theory of Computing (STOC), pages 77–82. ACM, 1987.

[64] Larry Stockmeyer and Albert R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753–784, 2002.

[65] Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. on Computing, 20(5):865–877, 1991.

[66] Alan M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc., s2-42(1):230–265, 1937.

[67] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162–176. Springer, 1977.

[68] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theor. Comput. Sci., 47(3):85–93, 1986.

[69] Dieter van Melkebeek. A survey of lower bounds for satisfiability and related problems. Foundations and Trends in Theoretical Computer Science, 2(3):197–303, 2006.

[70] Dieter van Melkebeek and Ran Raz. A time lower bound for satisfiability. Theor. Comput. Sci., 348(2-3):311–320, 2005.

[71] N. V. Vinodchandran. A note on the circuit complexity of PP. Theor. Comput. Sci., 347(1-2):415–418, 2005.

[72] Emanuele Viola. On approximate majority and probabilistic time. Computational Complexity, 18(3):337–375, 2009.

[73] Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009.

[74] Emanuele Viola. Reducing 3XOR to listing triangles, an exposition. Available at http://www.ccs.neu.edu/home/viola/, 2011.

[75] Emanuele Viola. Lower bounds for data structures with space close to maximum imply circuit lower bounds. Theory of Computing, 15:1–9, 2019. Available at http://www.ccs.neu.edu/home/viola/.

[76] Emanuele Viola. Pseudorandom bits and lower bounds for randomized turing machines. Theory of Computing, 18(10):1–12, 2022.