A Precise Version of a Time Hierarchy Theorem

Article type: Research Article

Authors: Ben-Amram, Amir M. | Jones, Neil D.

Affiliations: The Academic College of Tel-Aviv Yaffo, Tel-Aviv, Israel. amirben@server.mta.ac.il | Department of Computer Science (DIKU), The University of Copenhagen, Denmark. neil@diku.dk

Note: [] Address for correspondence: Department of Computer Science (DIKU), The University of Copenhagen, Universitetsparken 1, 2100 Copenhagen Ø, Denmark.

Abstract: Using a simple programming language as a computational model, Neil Jones has shown that a constant-factor time hierarchy exists: thus a constant-factor difference in time makes a difference in problem-solving power, unlike the situation with Turing machines. In this note we review this result and fill in the programming details in the proof, thus obtaining a precise version of the theorem with explicit constant factors. Specifically, multiplying the running time by 232 provably allows more decision problems to be solved.

Keywords: time complexity, hierarchy theorem, universal program

DOI: 10.3233/FI-1999-381201

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 1-15, 1999