LOGSPACE and PTIME characterized by programming languages

✍ Scribed by Neil D. Jones

• Book ID: 104326663
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 180 KB
• Volume: 228
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00357-0

✦ Synopsis

A programming approach to computability and complexity theory yields more natural deÿnitions 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 wellknown 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.