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

Article type: Research Article

Authors: Šíma, Jiří^* | Žák, Stanislav^†

Affiliations: Institute of Computer Science, The Czech Academy of Sciences, Prague, Czech Republic. [email protected], [email protected]

Note: [*] Research was partially supported by project GA ČR P202/12/G061 and RVO: 67985807. The presentation of this paper benefited from valuable comments of an anonymous reviewer.

Note: [†] Research was partially supported by project GA ČR P202/10/1333 and RVO: 67985807. Address for correspondence: Institute of Computer Science, The Czech Academy of Sciences, P.O. Box 5, 182 07 Prague 8, Czech Republic.

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

DOI: 10.3233/FI-2017-1526

Journal: Fundamenta Informaticae, vol. 152, no. 4, pp. 397-409, 2017