@Article{benamramjones00,
  author =       "A. Ben-Amram and N. D. Jones",
  title =        "Computational Complexity via Programming Languages:
                 Constant Factors Do Matter",
  journal =      "Acta Informatica",
  volume =       "37",
  pages =        "83--120",
  year =         "2000",
  keywords =     "time complexity, hierarchy theorem, universal
                 program",
  summary =      "We propose a simple programming language as a
                 computational model for fundamental studies in
                 complexity. We show that a constant-factor time
                 hierarchies exist for this model: thus a
                 constant-factor difference in time makes a difference
                 in problem-solving power, unlike the situation with
                 Turing machines. We give hierarchy theorems for
                 deterministic and non-deterministic programs, as well
                 as for tally sets. We also consider the effects some
                 modifications of the language may have on time
                 complexity of problems, and discuss the rationale of
                 using a programming language model in complexity. This
                 paper elaborates and extends the ideas presented in
                 Jones' STOC '93 article.",
  puf =          "Artikel optaget i tidsskrift",
}