COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS††Portions of this work were carried out at Carngie-Mellon University, while the authors were in the Department of Computer Science. Portions of these results were reported in preliminary form in [1].
- 1 January 1971
- book chapter
- Published by Elsevier
Abstract
No abstract availableThis publication has 15 references indexed in Scilit:
- On the Efficiency of AlgorithmsJournal of the ACM, 1970
- Dense and non-dense families of complexity classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- The operator gapPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- Two memory bounds for the recognition of primes by automataTheory of Computing Systems, 1969
- Toward a Theory of EnumerationsJournal of the ACM, 1969
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplicationThe Journal of Symbolic Logic, 1958