Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: universal program

Sortuj według:

Ogranicz wyniki do:

A precise version of a time hierarchy theorem

Ben-Amram A.M., Jones N.D.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

1-15

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.