LOGSPACE and PTIME characterized by programming languages
1999; Elsevier BV; Volume: 228; Issue: 1-2 Linguagem: Inglês
10.1016/s0304-3975(98)00357-0
ISSN1879-2294
Autores Tópico(s)Logic, Reasoning, and Knowledge
ResumoA 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.
Referência(s)