Natural Proofs

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

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

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.

Princeton, NJ 08540 Pittsburgh, PA 15212

và Steklov Mathematical Institute

Vavilova 42, 117966, GSP{1

Moscow, RUSSIA

Ngày 11 tháng 9, 1999

Tóm tắt

Chúng tôi đưa ra khái niệm chứng minh tự nhiên (natural proof). Chúng tôi lập luận rằng các chứng minh đã biết về cận dưới đối với độ phức tạp của các hàm Boolean tường minh trong các mô hình không đơn điệu (non-monotone) đều thuộc định nghĩa của chúng tôi về tính tự nhiên. Chúng tôi chỉ ra, dựa trên một giả thiết độ khó (hardness assumption), rằng các chứng minh tự nhiên không thể chứng minh các cận dưới siêu đa thức đối với các mạch tổng quát. Không cần giả thiết độ khó, chúng tôi có thể chỉ ra rằng chúng không thể chứng minh các cận dưới mũ (đối với các mạch tổng quát) cho bài toán logarit rời rạc. Chúng tôi chỉ ra rằng lớp yếu hơn gồm các chứng minh tự nhiên AC 0, vốn đủ để chứng minh các cận dưới đối với tính chẵn lẻ của Furst, Saxe, và Sipser, Yao, và Hastad, về bản chất không có khả năng chứng minh các cận của Razborov và Smolensky. Chúng tôi đưa ra một số bằng chứng hình thức cho thấy các chứng minh tự nhiên thực sự là tự nhiên bằng cách chỉ ra rằng mọi thước đo độ phức tạp hình thức có thể chứng minh các cận dưới siêu đa thức cho một hàm duy nhất thì cũng có thể làm điều đó cho hầu hết mọi hàm, đây là một trong hai yêu cầu của một chứng minh tự nhiên theo nghĩa của chúng tôi.

Được hỗ trợ bởi khoản tài trợ # 93-6-6 của Alfred P. Sloan Foundation, bởi khoản tài trợ # 93-011-16015 của Russian Foundation for Fundamental Research, và bởi một khoản tài trợ AMS-FSU

y Được hỗ trợ một phần bởi khoản tài trợ NSF 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 Tiếng Việt by gpt-5, against glossary version 6. Translated from the English.