zbMATH — the first resource for mathematics

Natural proofs. (English) Zbl 0884.68055
Summary: We introduce the notion of natural proof. We argue that the known proofs of lower bounds on the complexity of explicit Boolean functions in nonmonotone models fall within our definition of natural. We show, based on a hardness assumption, that natural proofs can not prove superpolynomial lower bounds for general circuits. Without the hardness assumption, we are able to show that they can not 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 sufficient to prove the parity lower bounds of Furst, Saxe, and Sipser, Yao, and Håstad 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 superpolynomial 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.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
natural proof
Full Text: DOI
[1] Ajtai, M., σ^1_1-formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48, (1983) · Zbl 0519.03021
[2] Alon, N.; Boppana, R., The monotone circuit complexity of Boolean functions, Combinatorica, 7, 1-22, (1987) · Zbl 0631.68041
[3] Andreev, A. E., On a method for obtaining lower bounds for the complexity of individual monotone functions, Soviet Math. Dokl., 31, 530-534, (1985) · Zbl 0616.94019
[4] Andreev, A. E., On one method of obtaining effective lower bounds of monotone complexity, Algebra i Logika, 26, 3-21, (1987) · Zbl 0643.94027
[5] Andreev, A. E., On a method for obtaining more than quadratic effective lower bounds for the complexity ofπ, Moscow Univ. Math. Bull., 42, 63-66, (1987) · Zbl 0645.94022
[6] Aspnes, J.; Beigel, R.; Furst, M.; Rudich, S., The expressive power of voting polynomials, Combinatorica, 14, 135-148, (1994) · Zbl 0845.68045
[7] Baker, T. P.; Gill, J.; Solovay, R., Relatizations of thePNP, SIAM J. Comput., 4, 431-442, (1975)
[8] Barrington, D. A., Technical report, (1986)
[9] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. Comput., 13, 850-864, (1984) · Zbl 0547.68046
[10] M. Bonet, T. Pitassi, R. Raz, Lower bounds for cutting planes proofs with small coefficients, Proceedings, 27th ACM Symposium on Theory of Computing, 1995, 575, 584 · Zbl 0925.03207
[11] Furst, M.; Saxe, J. B.; Sipser, M., Parity, circuits and the polynomial time hierarchy, Math. Syst. Theory, 17, 13-27, (1984) · Zbl 0534.94008
[12] Goldreich, O.; Goldwasser, S.; Micali, S., How to construct random functions, J. Assoc. Comput. Mach., 33, 792-807, (1986) · Zbl 0596.65002
[13] A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, G. Turan, Threshold circuits of bounded depth, Proceedings, 28th Symposium on Foundations of Computer Science, 1987, 99, 110
[14] J. Håstad, 1986, Computational Limitations on Small Depth Circuits, Massachusetts Institute of Technology
[15] J. Håstad, The shrinkage exponent is 2, Proceedings of the 34th IEEE FOCS, 1993, 114, 123 · Zbl 0907.68107
[16] R. Impagliazzo, M. Naor, Efficient cryptographic schemes provably as secure as subset sum, Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, 236, 243 · Zbl 0862.94015
[17] Karchmer, M.; Wigderson, A., Monotone circuits for connectivity require super-logarithmic depth, SIAM J. Disc. Math., 3, 255-265, (May 1990) · Zbl 0695.94021
[18] M. Karchmer, A. Wigderson, On span programs, Proceedings of the 8th Structure in Complexity Theory Annual Conference, 1993, 102, 111
[19] J. Krajı́ček, Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic, J. Symbolic Logic
[20] N. Linial, Y. Mansour, N. Nisanb, Constant depth circuits, Fourier transforms and learnability, Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, 574, 579
[21] Muroga, S., Threshold Logic and Its Applications, (1971), Wiley-Interscience New York · Zbl 0243.94014
[22] Nisan, N., Pseudorandom bits for constant depth circuits, Combinatorica, 11, 63-70, (1991) · Zbl 0732.68056
[23] Nisan, N.; Impagliazzo, R., The effect of random restrictions on formulae size, Random Structures and Algorithms, 4, 121-134, (1993) · Zbl 0771.68065
[24] Paterson, M. S.; Zwick, U., Shrinkage of De Morgan formulae under restriction, Random Structures and Algorithms, 4, 135-150, (1993) · Zbl 0771.68067
[25] P. Pudlák, Lower bounds for resolution and cutting planes proofs and monotone computations, J. Symbolic Logic
[26] Raz, R.; Wigderson, A., Monotone circuits for matching require linear depth, J. Assoc. Comput. Mach., 39, 736-744, (1992) · Zbl 0799.68077
[27] Razborov, A. A., Lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl., 31, 354-357, (1985) · Zbl 0621.94027
[28] Razborov, A. A., Lower bounds of monotone complexity of the logical permanent function, Math. Notes Acad. Sci. USSR, 37, 485-493, (1985) · Zbl 0584.94026
[29] Razborov, A. A., Lower bounds on the size of bounded-depth networks over a complete basis with logical addition, Math. Notes Acad. Sci. USSR, 41, 333-338, (1987) · Zbl 0632.94030
[30] Razborov, A. A., Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions, Math. Notes Acad. Sci. USSR, (1990) · Zbl 0801.68091
[31] Razborov, A., On submodular complexity measures, Boolean Function Complexity, Lecture Notes Ser., 169, (1992), Cambridge Univ. PressLondon Math. Soc Cambridge, p. 76-83 · Zbl 0770.68073
[32] A. Razborov, On small size approximation models, The Mathematics of Paul Erdős
[33] Razborov, A., Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic, Izv. Akad. Nauk SSSR, 59, 201-222, (1995) · Zbl 0838.03045
[34] Razborov, A., Technical Report RS-94-36, (1994)
[35] Razborov, A., Lower bounds for propositional proofs and independence results in bounded arithmetic, (Meyer auf der Heide, F; Monien, B., Proceedings, 23rd ICALP, Lecture Notes in Computer Science, 1099, (1996), Springer-Verlag New York/Berlin), 48-62 · Zbl 1045.03524
[36] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings, 19th ACM Symposium on Theory of Computing, 1987, 77, 82
[37] Tardos, É., The gap between monotone and nonmonotone circuit complexity is exponential, Combinatorica, 8, 141-142, (1988) · Zbl 0807.94026
[38] Wegener, I., The complexity of Boolean functions, (1987), Wiley-Teubner New York · Zbl 0623.94018
[39] Wigderson, A., The fusion method for lower bounds in circuit complexity, Combinatorics, Paul Erdős is Eighty, (1993), Elsevier Amsterdam · Zbl 0799.68082
[40] A. Yao, Separating the polynomial-time hierarchy by oracles, Proceedings, 26th IEEE POCS, 1985, 1, 10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.