Schnorr, C. P. The network complexity and the Turing machine complexity of finite functions. (English) Zbl 0338.02019 Acta Inf. 7, 95-107 (1976). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 1 ReviewCited in 27 Documents MSC: 03D10 Turing machines and related notions 68Q25 Analysis of algorithms and problem complexity 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) PDF BibTeX XML Cite \textit{C. P. Schnorr}, Acta Inf. 7, 95--107 (1976; Zbl 0338.02019) Full Text: DOI References: [1] Fischer, M. J.: Lectures on network complexity. Preprint Universität Frankfurt, June 1974 [2] Hennie, F. C., Stearns, R. E.: Two tape simulation of multitape turing machines. J. ACM 13, 533-546 (1966) · Zbl 0148.24801 [3] Lupanov, O. B.: Complexity of formula realisation of functions of logical algebra. Prob. Cybernetics 3 (1962) · Zbl 0196.51803 [4] Paterson, M. S., Fischer, M. J., Meyer, A. R.: An improved overlap argument for on-line multiplication. In: Complexity of Computation. SIAM AMS Proceedings 7, 97-111 (1974) · Zbl 0301.68059 [5] Savage, J. E.: Computational work and time on finite machines. J. ACM 19, 660-674 (1972) · Zbl 0251.68031 [6] Schnorr, C. P.: Lower bounds for the product of time and space requirements of Turing machine computations. Proc. Symposium on the Mathematical Foundations of Computer Science 1973, High Tatras. CSSR, Math. Inst. Slovak Academy of Sciences 1973, P. 153-161 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.