Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

A. A. Razborov

Izvestiya. Mathematics , Tome 59 (1995) no. 1, pp. 205-227.

Résumé

We show that if strong pseudorandom generators exist then the statement "$\alpha$ encodes a circuit of size $n^{(\log^*n)}$ for SATISFIABILITY" is not refutable in $S_2^2(\alpha)$. For refutation in $S_2^1(\alpha)$, this is proven under the weaker assumption of the existence of generators secure against the attack by small depth circuits, and for another system which is strong enough to prove exponential lower bounds for constant-depth circuits, this is shown without using any unproven hardness assumptions. These results can be also viewed as direct corollaries of interpolation-like theorems for certain “split versions” of classical systems of Bounded Arithmetic introduced in this paper. Bibliography: 36 titles.

Bibliographie

[1] Ajtai M., “$\Sigma _1^1$-formulae on finite structures”, Annals of Pure and Applied Logic, 24 (1983), 1–48 | DOI | MR | Zbl

[2] Alon N., Boppana R., “The monotone circuit complexity of Boolean functions”, Combinatorica, 7:1 (1987), 1–22 | DOI | MR | Zbl

[3] Aspnes J., Beigel R., Furst M., Rudich S., “The expressive power of voting polynomials”, Proceedings of the 23rd ACM STOC, 1991, 402–409; Combinatorica (to appear)

[4] Barrington D. A., A note on a theorem of Razborov, Technical report, University of Massachusetts, 1986

[5] Boppana R. B. and Sipser M., “The complexity of finite functions”, Handbook of Theoretical Computer Science. Vol. A. Algorithms and Complexity, chapter 14, eds. Jan van Leeuwen, Elsevier Science Publishers B.V.; The MIT Press, 1990, 757–804 | MR | Zbl

[6] Buss S. R., Bounded Arithmetic, Bibliopolis, Napoli, 1986 | MR | Zbl

[7] Buss S. R., “Axiomatizations and conservations results for fragments of Bounded Arithmetic”, Logic and Computation, Contemporary Mathematics, 106, American Math. Society, 1990, 57–84 | MR

[8] Buss S. R., Krajíc̆ek J., “An application of Boolean complexity to separation problems in Bounded Arithmetic”, Proceedings of the London Mathematical Society, 1992 (to appear) | MR

[9] Chiari M., Krajíc̆ek J., Witnesing functions in Bounded Arithmetic and search problems, Manuscript in preparation, 1994

[10] Cook S., “Feasibly constructive proofs and the propositional calculus”, Proceedings of the 7th Annual ACM Symposium on the Theory of Computing, 1975, 83–97 | MR | Zbl

[11] Furst M., Saxe J. B., Sipser M., “Parity, circuits and the polynomial time hierarchy”, Math. Syst. Theory, 17 (1984), 13–27 | DOI | MR | Zbl

[12] Håstad J., Computational limitations on Small Depth Circuits, PhD thesis, Massachusetts Institute of Technology, 1986 | Zbl

[13] Johnson D. S., Papadimitriou C. H., Yannakakis M., “How easy is local search {?}”, Journal of Computer and System Sciences, 37 (1988), 79–100 | DOI | MR | Zbl

[14] Karchmer M., Communication complexity: A new approach to circuit depth, PhD thesis, Massachusetts Institute of Technology, 1989 | MR

[15] Karchmer M., Wigderson A., “Monotone circuits for connectivity require super-logarithmic depth”, SIAM J. on Disc. Math., 3:2 (1990), 255–265 | DOI | MR | Zbl

[16] Paris J. B., Wilkie A. J., Woods A. R., “Provability of the pigeonhole principle and the existence of infinitely many primes”, Journal of Symbolic Logic, 53:4 (1988), 1235–1244 | DOI | MR | Zbl

[17] Raz R., Wigderson A., “Monotone circuits for matching require linear depth”, Proceedings of the 22th Ann. ACM Symposium on the Theory of Computing, 1990, 287–292

[18] Razborov A., “An equivalence between second order bounded domain bounded arithmetic and first order bounded arithmetic”, Arithmetic, Proof Theory and Computational Complexity, eds. Clote P., Krajíc̆ek J., Oxford University Press, 1992, 247–277 | MR

[19] Razborov A., “Bounded Arithmetic and lower bounds in Boolean complexity”, Feasible Mathematics, II, 1993 (to appear)

[20] Razborov A., Rudich S., “Natural proofs”, Proc. of the 26th ACM STOC, 204–213, Submitted to J. of Comp. and System Sci. | MR

[21] Smolensky R., “Algebraic methods in the theory of lower bounds for Boolean circuit complexity”, Proceedings of the 19th ACM Symposium on Theory of Computing, 1987, 77–82

[22] Takeuti G., “$S_3^i$ and $\overset \circ \to V{}_2^i(BD)$”, Archive for Math. Logic, 29 (1990), 149–169 | DOI | MR | Zbl

[23] Takeuti G., “$RSUV$ isomorphisms”, Arithmetic, Proof Theory and Computational Complexity, eds. Clote P., Krajíc̆ek J., Oxford University Press, 1992, 364–386 | MR

[24] Tardos É., “The gap between monotone and nonmonotone circuit complexity is exponential”, Combinatorica, 8 (1988), 141–142 | DOI | MR | Zbl

[25] Wilmers G., “Bounded existential induction”, The Journal of Symbolic Logic, 50:1 (1985), 72–90 | DOI | MR | Zbl

[26] Yao A., “Separating the polynomial-time hierarchy by oracles”, Proceedings of the 26th IEEE FOCS, 1985, 1–10

[27] Andreev A. E., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti individualnykh monotonnykh funktsii”, DAN SSSR, 282:5 (1985), 1033–1037 | MR | Zbl

[28] Andreev A. E., “Ob odnom metode polucheniya effektivnykh nizhnikh otsenok monotonnoi slozhnosti”, Algebra i logika, 26:1 (1987), 3–21 | MR

[29] Markov A. A., “O minimalnykh kontaktno-ventilnykh dvukhpolyusnikakh dlya monotonnykh simmetricheskikh funktsii”, Problemy kibernetiki, no. 8, Nauka, 1962, 117–121

[30] Nechiporuk E. I., “Ob odnoi bulevskoi funktsii”, DAN SSSR, 169:4 (1966), 765–766 ; Nečiporuk E. I., “On a Boolean function”, Soviet Mathematics Doklady, 7:4, 999–1000 | MR | Zbl

[31] Razborov A. A., “Nizhnie otsenki monotonnoi slozhnosti nekotorykh bulevykh funktsii”, DAN SSSR, 281:4 (1985), 798–801 | MR | Zbl

[32] Razborov A. A., “Nizhnie otsenki monotonnoi slozhnosti logicheskogo permanenta”, Matem. zametki, 37:6 (1985), 887–900 | MR | Zbl

[33] Razborov A. A., “Nizhnie otsenki razmera skhem ogranichennoi glubiny v polnom bazise, soderzhaschem funktsiyu logicheskogo slozheniya”, Matem. zametki, 41:4 (1987), 598–607 | MR | Zbl

[34] Subbotovskaya B. A., “O realizatsii lineinykh funktsii formulami v bazise $\,\lor,-$”, DAN SSSR, 136:3 (1961), 553–555 | Zbl

[35] Khrapchenko V. M., “O slozhnosti realizatsii lineinoi funktsii v klasse $\Pi $-skhem”, Matem. zametki, 9:1 (1971), 35–40 | MR | Zbl

[36] Khrapchenko V. M., “Ob odnom metode polucheniya nizhnikh otsenok slozhnosti $\Pi $-skhem”, Matem. Zametki, 10:1 (1971), 83–92 | MR | Zbl