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 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の一部支援を受けた

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.