RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. RAN. Ser. Mat., 1995, Volume 59, Issue 1, Pages 201–224 (Mi izv9)

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

A. A. Razborov

Institute for Advanced Study, School of Mathematics

Abstract: 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.

Full text: PDF file (4581 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 1995, 59:1, 205–227

Bibliographic databases:

MSC: 03C62
Language:

Citation: A. A. Razborov, “Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic”, Izv. RAN. Ser. Mat., 59:1 (1995), 201–224; Izv. Math., 59:1 (1995), 205–227

Citation in format AMSBIB
\Bibitem{Raz95} \by A.~A.~Razborov \paper Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic \jour Izv. RAN. Ser. Mat. \yr 1995 \vol 59 \issue 1 \pages 201--224 \mathnet{http://mi.mathnet.ru/izv9} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1328561} \zmath{https://zbmath.org/?q=an:0838.03045} \transl \jour Izv. Math. \yr 1995 \vol 59 \issue 1 \pages 205--227 \crossref{https://doi.org/10.1070/IM1995v059n01ABEH000009} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1995RZ88700009} 

• http://mi.mathnet.ru/eng/izv9
• http://mi.mathnet.ru/eng/izv/v59/i1/p201

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Pudlak P., “Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations”, J. Symb. Log., 62:3 (1997), 981–998
2. Razborov A., “Lower Bounds for the Polynomial Calculus”, Comput. Complex., 7:4 (1998), 291–324
3. Atserias A., Bonet M., “On the Automatizability of Resolution and Related Propositional Proof Systems”, Computer Science Logic, Proceedings, Lecture Notes in Computer Science, 2471, ed. Bradfield J., Springer-Verlag Berlin, 2002, 569–583
4. Albert Atserias, Marı́a Luisa Bonet, “On the automatizability of resolution and related propositional proof systems”, Information and Computation, 189:2 (2004), 182
5. Bonet M., Domingo C., Gavalda R., Maciel A., Pitassi T., “Non-Automatizability of Bounded-Depth Frege Proofs”, Comput. Complex., 13:1-2 (2004), 47–68
6. Allender E., “Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, eds. Hirsch E., Razborov A., Semenov A., Slissenko A., Springer-Verlag Berlin, 2008, 3–10
7. Pudlak P., “Twelve Problems in Proof Complexity”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 5010, eds. Hirsch E., Razborov A., Semenov A., Slissenko A., Springer-Verlag Berlin, 2008, 13–27
8. Allender E., Koucky M., “Amplifying Lower Bounds by Means of Self-Reducibility”, Twenty-Third Annual IEEE Conference on Computational Complexity, Proceedings, Annual IEEE Conference on Computational Complexity, IEEE Computer Soc, 2008, 31–40
9. Krajicek J., “A Form of Feasible Interpolation for Constant Depth Frege Systems”, J. Symb. Log., 75:2 (2010), 774–784
10. Allender E., Kouckuy M., “Amplifying Lower Bounds by Means of Self-Reducibility”, J. ACM, 57:3 (2010), 14
11. Alexander Razborov, “Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution”, Ann. Math, 181:2 (2015), 415
12. J.A.. Grochow, “Unifying Known Lower Bounds via Geometric Complexity Theory”, comput. complex, 2015
•  Number of views: This page: 311 Full text: 89 References: 32 First page: 3