LOGSPACE and PTIME characterized by programming languages

A programming approach to computability and complexity theory yields more natural definitions and proofs of central results than the classical approach. Further, some new results can be obtained using this viewpoint. This paper contains new intrinsic characterizations of the well-known complexity classes PTIME and LOGSPACE, with no externally imposed resource bounds on time or space. LOGSPACE is proven identical with the decision problems solvable by read-only imperative programs on Lisp-like lists; and PTIME is proven identical with the problems solvable by recursive read-only programs.

Authors

• Neil D. Jones

Keywords

• Complexity
• Read-only or cons-free programs
• PTIME
• LOGSPACE