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


03D10 Turing machines and related notions
68Q25 Analysis of algorithms and problem complexity
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI


[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 · doi:10.1145/321356.321362
[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 · doi:10.1145/321724.321731
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.