×

zbMATH — the first resource for mathematics

The network complexity and the Turing machine complexity of finite functions. (English) Zbl 0338.02019

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
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.