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

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)\).


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


Zbl 1059.03063
Full Text: DOI


[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.