Computational complexity via programming languages: constant factors do matter |
| |
Authors: | Amir M Ben-Amram Neil D Jones |
| |
Affiliation: | The Academic College of Tel Aviv, Computer Science Division, 4 Antokolski St., 64044 Tel Aviv, Israel (e-mail: amirben@server.mta.ac.il), IL The University of Copenhagen, Computer Science Department (DIKU), Universitetsparken 1, 2100 Copenhagen ? (e-mail: neil@diku.dk), DK
|
| |
Abstract: | The purpose of this work is to promote a programming-language approach to studying computability and complexity, with an
emphasis on time complexity. The essence of the approach is: a programming language, with semantics and complexity measure,
can serve as a computational model that has several advantages over the currently popular models and in particular the Turing
machine. An obvious advantage is a stronger relevance to the practice of programming. In this paper we demonstrate other advantages:
certain proofs and constructions that are hard to do precisely and clearly with Turing machines become clearer and easier in our approach, and sometimes lead
to finer results. In particular, we prove several time hierarchy theorems, for deterministic and non-deterministic time complexity which show that, in contrast with Turing machines, constant factors
do matter in this framework. This feature, too, brings the theory closer to practical considerations. The above result suggests
that this framework may be appropriate for studying low complexity classes, such as linear time. As an example we give a problem
complete for non-deterministic\/ linear time under deterministic linear-time reductions. Finally, we consider some extensions and modifications of our programming
language and their effect on time complexity results.
Received: 26 October 1998 / 9 June 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|