Cons-free Programs and Complexity Classes between LOGSPACE and PTIME

Neil D. Jones
(University of Copenhagen)
Siddharth Bhaskar
(University of Copenhagen)
Cynthia Kop
(Radboud University, Nijmegen)
Jakob Grue Simonsen
(University of Copenhagen)

Programming language concepts are used to give some new perspectives on a long-standing open problem: is logspace = ptime ?

In Laurent Fribourg and Matthias Heizmann: Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis (VPT/HCVS 2020), Dublin, Ireland, 25-26th April 2020, Electronic Proceedings in Theoretical Computer Science 320, pp. 65–79.
Published: 7th August 2020.

ArXived at: http://dx.doi.org/10.4204/EPTCS.320.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org