A compendium of problems complete for symmetric logarithmic space

Authors
Alvarez, C Greenlaw, R
Citation
C. Alvarez et R. Greenlaw, A compendium of problems complete for symmetric logarithmic space, COMP COMPLE, 9(2), 2000, pp. 123-145
Citations number
38
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL COMPLEXITY
ISSN journal
10163328 → ACNP
Volume
9
Issue
2
Year of publication
2000
Pages
123 - 145
Database
ISI
SICI code
1016-3328(2000)9:2<123:ACOPCF>2.0.ZU;2-A
Abstract
The paper's main contributions are a compendium of problems that are comple te for symmetric logarithmic space (SL), a collection of material relating to SL, a list of open problems, and an extension to the number of problems known to be SL-complete. Complete problems are one method of studying SL, a class for which programming is nonintuitive. Our exposition helps make the class SL less mysterious and more accessible to other researchers.