A precise version of a time hierarchy theorem

• Autorzy: Ben-Amram A.M. , Jones N.D.
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

time complexity; hierarchy theorem; universal program

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 1--15
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Ben-Amram A.M.

autor

Jones N.D.

• Department of Computer Science (DIKU), The University of Copenhagen, Universitetsparken 1, 2100 Copenhagen O, Denmark,