Paper Info
Title
Computational complexity via programming languages: constant factors do matter
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.
Year
DOI
Venue
2000
10.1007/s002360000038
Acta Inf.
Keywords
Field
DocType
constant factor,programming language,computational complexity,computer model,turing machine,linear time,time complexity
2-EXPTIME,Complexity class,DTIME,Structural complexity theory,Programming language,EXPTIME,Computer science,NP-easy,Theoretical computer science,Time hierarchy theorem,Computational complexity theory
Journal
Volume
Issue
ISSN
37
2
0001-5903
Citations 
PageRank 
References 
7
0.68
22
Authors
2
Name
Order
Citations
PageRank
Amir M Ben-Amram132730.52
Neil D. Jones22634558.61