Natural Proofs
- 1 August 1997
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 55 (1) , 24-35
- https://doi.org/10.1006/jcss.1997.1494
Abstract
No abstract availableKeywords
This publication has 30 references indexed in Scilit:
- Lower bounds for cutting planes proofs with small coefficientsPublished by Association for Computing Machinery (ACM) ,1995
- The expressive power of voting polynomialsCombinatorica, 1994
- Threshold circuits of bounded depthPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- The monotone circuit complexity of boolean functionsCombinatorica, 1987
- A method for obtaining efficient lower bounds for monotone complexityAlgebra and Logic, 1987
- How to construct random functionsJournal of the ACM, 1986
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975