Some Complexity Results Interesting from a Programming Viewpoint

Neil D. Jones

University of Copenhagen

Abstract
  1. For a natural programming language I, and any a > = 1TIME(229 an) properly contains TIME(an)
  2. From 1997 book, and TCS 98:
    LOGSPACE = sets decided by tail recursive read-only programs
    PTIME = sets decided by recursive read-only programs

Interesting contrasts:

Left sides = extrinsic characterizations, right sides = intrinsic characterizations.

Recursive read-only programs DECIDE only PTIME problems, but RUN in exponential time.

This major mismatch between intensional and extensional complexity should be better understood. It seems to imply that restriction to pure functional programming style can have major efficiency consequences - IF the time differences can be proven to be necessary.

References:
  1. Neil Jones STOC 93, since refined a bit.
  2. Computability and Complexity from a Programming Perspective, Neil Jones, MIT Press, 1997
  3. Stephen Cook 1971, 1972: 2-way auxiliary pushdown automata
  4. Andreas Goerdt, TCS and Information & Computation, Characterizing Complexity Classes by Higher Type Recursive Definitions

Joan Lockwood, Department of Computer Science, Cornell University, Ithaca, NY. Mail to: joan@cs.cornell.edu