Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution. (English) Zbl 1376.03055

Razborov, Alexander A.

Ann. Math. (2) 181, No. 2, 415-472 (2015).

Summary: A pseudorandom generator \(G_n:\{0,1\}^n\to \{0,1\}^m\) is hard for a propositional proof system \(P\) if (roughly speaking) \(P\) cannot efficiently prove the statement \(G_n(x_1,\ldots,x_n)\neq b\) for any string \(b\in\{0,1\}^m\). We present a function \((m\geq 2^{n^{\Omega(1)}})\) generator which is hard for \(\mathrm{Res}(\varepsilon\log n)\); here \(\mathrm{Res}(k)\) is the propositional proof system that extends Resolution by allowing \(k\)-DNFs instead of clauses.
As a direct consequence of this result, we show that whenever \(t\geq n^2\), every \(\mathrm{Res}(\varepsilon\log t)\) proof of the principle \(\neg \mathrm{Circuit}_t(f_n)\) (asserting that the circuit size of a Boolean function \(f_n\) in \(n\) variables is greater than \(t\)) must have size \(\exp(t^{\Omega(1)})\). In particular, \(\mathrm{Res}(\log \log N)\) (\(N\sim 2^n\) is the overall number of propositional variables) does not possess efficient proofs of \(\mathbf{NP}\not\subseteq \mathbf{P}/\mathrm{poly}\). Similar results hold also for the system PCR (the natural common extension of Polynomial Calculus and Resolution) when the characteristic of the ground field is different from 2.
As a byproduct, we also improve on the small restriction switching lemma due to N. Segerlind et al. [SIAM J. Comput. 33, No. 5, 1171–1200 (2004; Zbl 1059.03063)] by removing a square root from the final bound. This in particular implies that the (moderately) weak pigeonhole principle \(\mathrm{PHP}^{2n}_n\) is hard for \(\mathrm{Res}(\varepsilon\log n/\log\log n)\).

MSC:

03F20	Complexity of proofs
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

proof complexity; pseudorandom generators

Citations:

Zbl 1059.03063

References:

[1]	A. Atserias, M. L. Bonet, and J. L. Esteban, ”Lower bounds for the weak pigeonhole principle and random formulas beyond Resolution,” Inform. and Comput., vol. 176, iss. 2, pp. 136-152, 2002. · Zbl 1012.03058
[2]	M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, and A. Wigderson, ”Space complexity in propositional calculus,” SIAM J. Comput., vol. 31, iss. 4, pp. 1184-1211, 2002. · Zbl 1004.03047
[3]	M. Alekhnovich, E. Ben-Sasson, A. A. Razborov, and A. Wigderson, ”Pseudorandom generators in propositional proof complexity,” SIAM J. Comput., vol. 34, iss. 1, pp. 67-88, 2004. · Zbl 1096.03070
[4]	M. V. Alekhnovich and A. A. Razborov, ”Lower bounds for polynomial calculus: the nonbinomial ideal case,” Tr. Mat. Inst. Steklova, vol. 242, iss. Mat. Logika i Algebra, pp. 23-43, 2003. · Zbl 1079.03047
[5]	N. Alon and J. H. Spencer, The probabilistic method, Third ed., Hoboken, NJ: John Wiley & Sons, 2008. · Zbl 1148.05001
[6]	R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, ”Quantum lower bounds by polynomials,” J. ACM, vol. 48, pp. 778-797, 2001. · Zbl 1127.68404
[7]	S. Buss, D. Grigoriev, R. Impagliazzo, and T. Pitassi, ”Linear gaps between degrees for the polynomial calculus modulo distinct primes,” J. Comput. System Sci., vol. 62, iss. 2, pp. 267-289, 2001. · Zbl 1007.03052
[8]	E. Ben-Sasson and R. Impagliazzo, ”Random CNF’s are hard for the polynomial calculus,” Comput. Complexity, vol. 19, iss. 4, pp. 501-519, 2010. · Zbl 1216.03064
[9]	P. Beame and T. Pitassi, ”Simplified and improved resolution lower bounds,” in 37th Annual Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Comput. Soc. Press, 1996, pp. 274-282. · Zbl 0866.03029
[10]	P. Beame and T. Pitassi, ”Propositional proof complexity: past, present, and future,” in Current Trends in Theoretical Computer Science, River Edge, NJ: World Sci. Publ., 2001, pp. 42-70. · Zbl 1049.03040
[11]	M. Bonet, T. Pitassi, and R. Raz, ”Lower bounds for cutting planes proofs with small coefficients,” J. Symbolic Logic, vol. 62, iss. 3, pp. 708-728, 1997. · Zbl 0889.03050
[12]	M. L. Bonet, T. Pitassi, and R. Raz, ”On interpolation and automatization for Frege systems,” SIAM J. Comput., vol. 29, iss. 6, pp. 1939-1967, 2000. · Zbl 0959.03044
[13]	S. R. Buss and G. Turán, ”Resolution proofs of generalized pigeonhole principles,” Theoret. Comput. Sci., vol. 62, iss. 3, pp. 311-317, 1988. · Zbl 1007.03052
[14]	M. Clegg, J. Edmonds, and R. Impagliazzo, ”Using the Groebner basis algorithm to find proofs of unsatisfiability,” in Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, New York, 1996, pp. 174-183. · Zbl 0938.68825
[15]	M. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson, ”Randomness conductors and constant-degree lossless expanders,” in Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, 2002, pp. 659-668. · Zbl 1192.68475
[16]	O. Goldreich, S. Goldwasser, and S. Micali, ”How to construct random functions,” J. Assoc. Comput. Mach., vol. 33, iss. 4, pp. 792-807, 1986. · Zbl 0596.65002
[17]	O. Goldreich, ”Candidate one-way functions based on expander graphs,” in Studies in Complexity and Cryptography, New York: Springer-Verlag, 2011, vol. 6650, pp. 76-87. · Zbl 1306.94056
[18]	R. Impagliazzo, V. Kabanets, and A. Wigderson, ”In search of an easy witness: exponential time vs. probabilistic polynomial time,” J. Comput. System Sci., vol. 65, iss. 4, pp. 672-694, 2002. · Zbl 1059.68047
[19]	S. Janson, ”Poisson approximation for large deviations,” Random Structures Algorithms, vol. 1, iss. 2, pp. 221-229, 1990. · Zbl 0747.05079
[20]	J. Kraj’ivcek and P. Pudlák, ”Some consequences of cryptographical conjectures for \({ S}^1_2\) and \({ EF}\),” Inform. and Comput., vol. 140, iss. 1, pp. 82-94, 1998. · Zbl 0892.68029
[21]	J. Kraj’ivcek, Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge: Cambridge Univ. Press, 1995, vol. 60. · Zbl 0835.03025
[22]	J. Kraj’ivcek, ”Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic,” J. Symbolic Logic, vol. 62, iss. 2, pp. 457-486, 1997. · Zbl 0891.03029
[23]	J. Kraj’ivcek, ”Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus,” in Mathematical Foundations of Computer Science 1997, New York: Springer-Verlag, 1997, vol. 1295, pp. 85-90. · Zbl 0935.03068
[24]	J. Kraj’ivcek, ”On the weak pigeonhole principle,” Fund. Math., vol. 170, iss. 1-2, pp. 123-140, 2001. · Zbl 0987.03051
[25]	J. Kraj’ivcek, ”Tautologies from pseudo-random generators,” Bull. Symbolic Logic, vol. 7, iss. 2, pp. 197-212, 2001. · Zbl 0983.03046
[26]	J. Kraj’ivcek, ”Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds,” J. Symbolic Logic, vol. 69, iss. 1, pp. 265-286, 2004. · Zbl 1068.03048
[27]	N. Nisan, ”CREW PRAMs and decision trees,” SIAM J. Comput., vol. 20, iss. 6, pp. 999-1007, 1991. · Zbl 0737.68028
[28]	N. Nisan and A. Wigderson, ”Hardness vs. randomness,” J. Comput. System Sci., vol. 49, iss. 2, pp. 149-167, 1994. · Zbl 0821.68057
[29]	M. Pinsker, ”On the complexity of a concentrator,” in 7th Annual Teletraffic Conference, Stockholm: , 1973, p. 318/1-318/4.
[30]	P. Pudlák, ”Lower bounds for resolution and cutting plane proofs and monotone computations,” J. Symbolic Logic, vol. 62, iss. 3, pp. 981-998, 1997. · Zbl 0945.03086
[31]	P. Pudlák, ”The lengths of proofs,” in Handbook of Proof Theory, Amsterdam: North-Holland, 1998, pp. 547-637. · Zbl 0920.03056
[32]	R. Raz, ”Resolution lower bounds for the weak pigeonhole principle,” J. ACM, vol. 51, iss. 2, pp. 115-138, 2004. · Zbl 1063.03044
[33]	A. A. Razborov, ”Bounded arithmetic and lower bounds in Boolean complexity,” in Feasible Mathematics, II, Boston: Birkhäuser, 1995, vol. 13, pp. 344-386. · Zbl 0838.03044
[34]	A. A. Razborov, ”Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic,” Izv. Ross. Akad. Nauk Ser. Mat., vol. 59, iss. 1, pp. 201-224, 1995. · Zbl 0838.03045
[35]	A. A. Razborov, ”Lower bounds for propositional proofs and independence results in bounded arithmetic,” in Automata, Languages and Programming, New York: Springer-Verlag, 1996, vol. 1099, pp. 48-62. · Zbl 1045.03524
[36]	A. A. Razborov, ”Lower bounds for the polynomial calculus,” Comput. Complexity, vol. 7, iss. 4, pp. 291-324, 1998. · Zbl 1026.03043
[37]	A. A. Razborov, ”Proof complexity of pigeonhole principles,” in Developments in Language Theory, New York: Springer-Verlag, 2002, vol. 2295, pp. 110-116. · Zbl 1073.03540
[38]	A. A. Razborov, ”Resolution lower bounds for perfect matching principles,” J. Comput. System Sci., vol. 69, iss. 1, pp. 3-27, 2004. · Zbl 1106.03049
[39]	A. A. Razborov and S. Rudich, ”Natural proofs,” J. Comput. System Sci., vol. 55, iss. 1, part 1, pp. 24-35, 1997. · Zbl 0884.68055
[40]	N. Segerlind, S. Buss, and R. Impagliazzo, ”A switching lemma for small restrictions and lower bounds for \(k\)-DNF resolution,” SIAM J. Comput., vol. 33, iss. 5, pp. 1171-1200, 2004. · Zbl 1059.03063
[41]	A. Urquhart, ”The complexity of propositional proofs,” Bull. Symbolic Logic, vol. 1, iss. 4, pp. 425-467, 1995. · Zbl 0845.03025
[42]	A. C. Yao, ”Theory and applications of trapdoor functions,” in 23rd Annual Symposium on Foundations of Computer Science, New York: IEEE, 1982, pp. 80-91.