Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
1--15
Opis fizyczny
bibliogr. 9 poz.
Twórcy
autor
autor
- Department of Computer Science (DIKU), The University of Copenhagen, Universitetsparken 1, 2100 Copenhagen O, Denmark, amirben@server.mta.ac.i
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS1-0007-0025