On Tight Separation for Blum Measures Applied to Turing Machine Buffer Complexity

• Autorzy: Šíma J. , Žák S.

Identyfikatory

DOI

10.3233/FI-2017-1526

• Języki publikacji: EN

Abstrakty

EN

We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that a very small increase in the distance or buffer complexity bound (roughly from f(n) to f(n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes.

Słowa kluczowe

EN

turing machines; machine theory; unary algebra; cache memory; computer storage devices

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 4
• Strony: 397--409
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Šíma J.

• Institute of Computer Science, The Czech Academy of Sciences, Prague, Czech Republic

autor

Žák S.

• Institute of Computer Science, The Czech Academy of Sciences, Prague, Czech Republic

Bibliografia

• [1] Trakhtenbrot BA. Turing computations with logarithmic delay. Algebra i Logika, 1964. 3(4):33–48.
• [2] Stearns RE, Hartmanis J, Lewis II PM. Hierarchies of Memory Limited Computations. In: Proceedings of the SWCT 1965 Sixth Annual Symposium on Switching Circuit Theory and Logical Design. 1965 pp. 179–190. doi:10.1109/FOCS.1965.11.
• [3] Borodin A. Computational Complexity and the Existence of Complexity Gaps. Journal of the ACM, 1972. 19(1):158–174. doi:10.1145/321679.321691.
• [4] Cook SA. A Hierarchy for Nondeterministic Time Complexity. Journal of Computer and System Sciences, 1973. 7(4):343–353. doi:10.1016/S0022-0000(73)80028-5.
• [5] Ibarra OH. A Hierarchy Theorem for Polynomial-Space Recognition. SIAM Journal on Computing, 1974. 3(3):184–187. doi:10.1137/0203014.
• [6] Seiferas JI. Relating Refined Space Complexity Classes. Journal of Computer and System Sciences, 1977. 14(1):100–129. doi:10.1016/S0022-0000(77)80042-1.
• [7] Seiferas JI, Fischer MJ, Meyer AR. Separating Nondeterministic Time Complexity Classes. Journal of the ACM, 1978. 25(1):146–167. doi:10.1145/322047.322061.
• [8] Sudborough IH. Separating Tape Bounded Auxiliary Pushdown Automata Classes. In: Proceedings of the STOC’77 Ninth Annual ACM Symposium on Theory of Computing. 1977 pp. 208–217. doi:10.1145/800105.803410.
• [9] Žák S. A Turing Machine Time Hierarchy. Theoretical Computer Science, 1983. 26:327–333. doi:10.1016/0304-3975(83)90015-4.
• [10] Allender E, Beigel R, Hertrampf U, Homer S. Almost-Everywhere Complexity Hierarchies for Nondeterministic Time. Theoretical Computer Science, 1993. 115(2):225–241. doi:10.1016/0304-3975(93)90117-C.
• [11] Geffert V. Space Hierarchy Theorem Revised. In: Proceedings of the MFCS 2001 Twenty-Sixth Symposium on Mathematical Foundations of Computer Science, volume 2136 of LNCS. 2001 pp. 387–397. doi:10.1007/3-540-44683-4_34.
• [12] Kinne J, van Melkebeek D. Space Hierarchy Results for Randomized Models. In: Proceedings of the STACS 2008 Twenty-Fifth Annual Symposium on Theoretical Aspects of Computer Science. 2008 pp. 433–444. doi:10.4230/LIPIcs.STACS.2008.1363.
• [13] Blum M. A Machine-Independent Theory of the Complexity of Recursive Functions. Journal of the ACM, 1967. 14(2):322–336. doi:10.1145/321386.321395.
• [14] Sipser M. Introduction to the Theory of Computation. International Thomson Publishing, 1st edition, 1996. ISBN 053494728X. doi:10.1145/230514.571645.
• [15] Žák S, Šíma J. A Turing Machine Distance Hierarchy. In: Proceedings of the LATA 2013 Seventh International Conference on Language and Automata Theory and Applications, volume 7810 of LNCS. 2013 pp. 570–578. doi:10.1007/978-3-642-37064-9_50.
• [16] Freedman AR, Ladner RE. Space Bounds for Processing Contentless Inputs. Journal of Computer and System Sciences, 1975. 11(1):118–128. doi:10.1016/S0022-0000(75)80052-3.
• [17] Geffert V. Nondeterministic Computations in Sublogarithmic Space and Space Constructibility. SIAM Journal on Computing, 1991. 20(3):484–498. doi:10.1137/0220031.
• [18] Žák S. A Turing Machine Space Hierarchy. Kybernetika, 1979. 15(2):100–121.
• [19] Žák S. A Turing Machine Oracle Hierarchy, Parts I and II. Commentationes Mathematicae Universitatis Carolinae, 1980. 21(1):11–39.