Natural Proofs

Alexander A. Razborov, Steven Rudich, 1997, Journal of Computer and System Sciences

About this paperTiếng Việt中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

日本語
English

自然な証明

Alexander A. Razborov Steven Rudich y School of Mathematics Computer Science Department Institute for Advanced Study Carnegie Mellon University

Princeton, NJ 08540 Pittsburgh, PA 15212

and Steklov Mathematical Institute

Vavilova 42, 117966, GSP{1

Moscow, RUSSIA

1999年9月11日

要旨

自然な証明という概念を導入する。非単調モデルにおける明示的なブール関数の計算量に対する既知の下界の証明が、自然の定義に該当することを論じる。困難性の仮定に基づき、自然な証明では一般回路に対する超多項式下界を証明できないことを示す。困難性の仮定なしでは、離散対数問題について、（一般回路に対する）指数下界を証明できないことを示すことができる。Furst、Saxe、Sipser、Yao、およびHastadのパリティ下界を証明するのに十分な、より弱いAC 0 -自然な証明のクラスは、RazborovとSmolenskyの下界を証明することが本質的に不可能であることを示す。自然な証明が実際に自然であることの形式的な証拠をいくつか与える。すなわち、単一の関数に対して超多項式下界を証明できる任意の形式的計算量尺度は、ほぼすべての関数に対してもそれを行うことができることを示す。これは、この意味での自然な証明における2つの要件のうちの1つである。

Alfred P. Sloan Foundationの助成金 # 93-6-6、Russian Foundation for Fundamental Researchの助成金 # 93-011-16015、およびAMS-FSU grantの支援を受けた

y NSF grant CCR-9119319の一部支援を受けた

Princeton, NJ 08540 Pittsburgh, PA 15212 and Steklov Mathematical Institute

Vavilova 42, 117966, GSP{1

Moscow, RUSSIA

September 11, 1999

Abstract

We introduce the notion of natural proof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in non-monotone models fall within our de nition of natural. We show based on a hardness assumption that natural proofs can't prove super-polynomial lower bounds for general circuits. Without the hardness assumption, we are able to show that they can't prove exponential lower bounds (for general circuits) for the discrete logarithm problem. We show that the weaker class of AC 0 -natural proofs which is sucient to prove the parity lower bounds of Furst, Saxe, and Sipser, Yao, and Hastad is inherently incapable of proving the bounds of Razborov and Smolensky. We give some formal evidence that natural proofs are indeed natural by showing that every formal complexity measure which can prove super-polynomial lower bounds for a single function, can do so for almost all functions, which is one of the two requirements of a natural proof in our sense.

Supported by the grant # 93-6-6 of the Alfred P. Sloan Foundation, by the grant # 93-011-16015 of the Russian Foundation for Fundamental Research, and by an AMS-FSU grant y Partially supported by NSF grant CCR-9119319

This section is missing here.

1 Introduction

This section is missing here.

2 Natural proofs

This section is missing here.

3 Examples of naturalizing arguments

This section is missing here.

4 Inherent limitations of natural proofs

This section is missing here.

5 **One property of formal complexity measures**

This section is missing here.

6 Conclusion

This section is missing here.

7 Acknowledgements

References

  1. M. Ajtai. 1 -formulae on nite structures. Annals of Pure and Applied Logic , 24:1{48, 1 May 1983.
  2. N. Alon and R. Boppana. The monotone circuit complexity of Boolean functions. Combinatorica , 7(1):1{22, 1987.
  3. A.E. Andreev . Ob odnom metode poluqeni ninih ocenok slonosti individual~nyh monotonnyh funkci\$i . DAN SSSR , 282(5):1033{1037, 1985. A.E. Andreev, On a method for obtaining lower bounds for the complexity of individual monotone functions. Soviet Math. Dokl. 31(3):530-534, 1985.
  4. A.E. Andreev . Ob odnom metode poluqeni ffektivnyh ninih ocenok monotonno\$i slonosti . Algebra i logika , 26(1):3{21, 1987. A.E. Andreev, On one method of obtaining e ective lower bounds of monotone complexity. Algebra i logika , 26(1):3-21, 1987. In Russian.
  5. A.E. Andreev . O metode poluqeni bolee qem kvadratiqnyh ninih ocenok dl slonosti -shem . Vestnik MGU, ser. matem i mehan. , 42(1):63{66, 1987. A.E. Andreev, On a method for obtaining more than quadratic e ective lower bounds for the complexity of -schemes. Moscow Univ. Math. Bull. 42(1):63-66, 1987. In Russian.
  6. J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The expressive power of voting polynomials. Combinatorica , 14(2):135{148, 1994.
  7. T.P. Baker, J. Gill, and R. Solovay. Relativizations of the P = NP question. SIAM Journal on Computing , 4:431{442, 1975.
  8. D. A. Barrington. A note on a theorem of Razborov. Technical report, University of Massachusetts, 1986.
  9. M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing , 13:850{864, 1984.
  10. M. Bonet, T. Pitassi, and R. Raz. Lower bounds for cutting planes proofs with small coecients. In Proceedings of the 27 th ACM Simposium on Theory of Computing , pages 575{584, 1995.
  11. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Math. Syst. Theory , 17:13{27, 1984.
  12. O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM , 33(4):792{807, 1986.
  13. A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, G. Turan. Threshold circuits of bounded depth. In Proceedings of the 28 th IEEE Symposium on Foundations of Computer Science , pages 99{110, 1987.
  14. J. Hastad. Computational limitations on Small Depth Circuits . PhD thesis, Massachusetts Institute of Technology, 1986.
  15. J. Hastad. The shrinkage exponent is 2. In Proceedings of the 34 th IEEE FOCS , pages 114{123, 1993. Journal version submitted to SIAM Journal on Computing .
  16. R. Impagliazzo and M. Naor. Ecient cryptographic schemes provably as secure as subset sum. In Proceedings of the 30 th IEEE Symposium on Foundations of Computer Science , pages 236{243, 1989.
  17. M. Karchmer and A. Wigderson. Monotone circuits for connectivity require superlogarithmic depth. SIAM J. on Disc. Math. , 3(2):255{265, May 1990.
  18. M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8 th Structure in Complexity Theory Annual Conference , pages 102{111, 1993.
  19. J. Kraji c ek. Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. Submitted to Journal of Symbolic Logic , 1994.
  20. N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transforms and learnability. In Proceedings of the 30 th IEEE Symposium on Foundations of Computer Science , pages 574{579, 1989.
  21. S. Muroga. Threshold logic and its applications . Wiley-Interscience, 1971.
  22. N. Nisan. Pseudorandom bits for constant depth circuits. Combinatorica , 11(1):63{70, 1991.
  23. N. Nisan and R. Impagliazzo. The e ect of random restrictions on formulae size. Random Structures and Algorithms , 4(2):121{134, 1993.
  24. M. S. Paterson and U. Zwick. Shrinkage of de Morgan formulae under restriction. Random Structures and Algorithms , 4(2):135{150, 1993.
  25. P. Pudlak. Lower bounds for resolution and cutting planes proofs and monotone computations. To appear in J. of Symbolic Logic , 1995.
  26. R. Raz and A. Wigderson. Monotone circuits for matching require linear depth. Journal of the ACM , 39:736{744, 1992.
  27. A. A. Razborov . Ninie ocenki monotonno\$i slonosti nekotoryh bulevyh funkci\$i . DAN SSSR , 281(4):798{801, 1985. A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. , 31:354-357, 1985.
  28. A. A. Razborov . Ninie ocenki monotonno\$i slonosti logiqeskogo permanenta . Matem. Zam. , 37(6):887{900, 1985. A. A. Razborov, Lower bounds of monotone complexity of the logical permanent function, Mathem. Notes of the Academy of Sci. of the USSR , 37:485-493, 1985.
  29. A. A. Razborov . Ninie ocenki razmera shem ograniqenno\$i glubiny v polnom bazise, soderawem funkci logiqeskogo sloeni . Matem. Zam. , 41(4):598{607, 1987. A. A. Razborov, Lower bounds on the size of bounded-depth networks over a complete basis with logical addition, Mathem. Notes of the Academy of Sci. of the USSR , 41(4):333-338, 1987.
  30. A. A. Razborov . Ninie ocenki slonosti realizacii simmetriqeskih bulevyh funkci\$i kontaktno-ventil~nymi shemami . Matem. Zam. , 48(6):79{ 91, 1990. A. A. Razborov, Lower bounds on the size of switching-and-recti er networks for symmetric Boolean functions, Mathem. Notes of the Academy of Sci. of the USSR .
  31. A. Razborov. On submodular complexity measures. In M. S. Paterson, editor, Boolean Function Complexity. London Math. Soc., Lecture Note Series 169, pages 76{83. Cambridge University Press, 1992.
  32. A. Razborov. On small size approximation models. To appear in the volume The Mathematics of Paul Erdos , 1993.
  33. A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of Bounded Arithmetic. Izv. AN SSSR, ser. matem. ( Izvestiya of the RAN ), 59(1):201{222, 1995.
  34. A. Razborov. On provably disjoint NP -pairs. Technical Report RS-94-36, Basic Research in Computer Science Center, Aarhus, Denmark, 1994.
  35. A. Razborov. Lower bounds for propositional proofs and independence results in Bounded Arithmetic. In F. Meyer auf der Heide and B. Monien, editors, Proceedings of the 23 rd ICALP, Lecture Notes in Computer Science, 1099, pages 48{62, New York/Berlin, 1996. Springer-Verlag.
  36. R. Smolensky. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on Theory of Computing , pages 77{82, 1987.
  37. E . Tardos. The gap between monotone and nonmonotone circuit complexity is exponential. Combinatorica , 8:141{142, 1988.
  38. I. Wegener. The complexity of Boolean functions . Wiley-Teubner, 1987.
  39. A. Wigderson. The fusion method for lower bounds in circuit complexity. In Combinatorics, Paul Erdos is Eighty . 1993.
  40. A. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26 th IEEE FOCS , pages 1{10, 1985.

Read off the page by the text layer of the PDF using pdftotext version 26.09.0. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.