Natural Proofs

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

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

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.

自然证明

Alexander A. Razborov Steven Rudich y 数学系 计算机科学系 高等研究院 卡内基梅隆大学

Princeton, NJ 08540 Pittsburgh, PA 15212

以及 Steklov Mathematical Institute

Vavilova 42, 117966, GSP{1

Moscow, RUSSIA

September 11, 1999

摘要

我们引入自然证明的概念。我们论证，关于非单调模型中显式布尔函数复杂度下界的已知证明，都属于我们所定义的自然证明。我们基于一个困难性假设证明，自然证明无法为一般电路证明超多项式下界。在没有该困难性假设的情况下，我们能够证明，对于离散对数问题，自然证明无法为一般电路证明指数下界。我们证明，较弱的 AC 0 -自然证明类足以证明 Furst、Saxe 和 Sipser、Yao 以及 Hastad 的奇偶性下界，但从本质上无法证明 Razborov 和 Smolensky 的下界。我们还给出了一些形式上的证据，表明自然证明确实是自然的：任何能够为单个函数证明超多项式下界的形式复杂度度量，也能够为几乎所有函数做到这一点，而这正是我们意义下自然证明的两个要求之一。

由 Alfred P. Sloan Foundation 的资助 # 93-6-6、Russian Foundation for Fundamental Research 的资助 # 93-011-16015 以及 AMS-FSU grant 资助

y 部分得到 NSF grant CCR-9119319 的资助

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.