Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style
icon Submit Paper


RSS-Feed
REPORTS > DETAIL:

Paper:

TR96-039 | 27th June 1996 00:00

A Compendium of Problems Complete for Symmetric Logarithmic Space

Contact
Add Comment
RSS-Feed




TR96-039 Authors: Carme Alvarez, Raymond Greenlaw
Publication: 15th July 1996 23:27
Downloads: 3947
Keywords: 


Abstract:

We provide a compendium of problems that are complete for
symmetric logarithmic space (SL). Complete problems are one method
of studying this class for which programming is nonintuitive. A
number of the problems in the list were not previously known to be
complete. A list containing a variety of open problems is also given.


Comment(s):

Comment #1 to TR96-039 | 13th September 1996 16:27

Figure 1 revised and Problem 4.3 correction Comment on: TR96-039





Comment #1 Authors: Carme Alvarez, Raymond Greenlaw
Accepted on: 13th September 1996 16:27
Downloads: 2264
Keywords: 


Abstract:

We provide a compendium of problems that are complete for
symmetric logarithmic space (SL). Complete problems are one method
of studying this class for which programming is nonintuitive. A
number of the problems in the list were not previously known to be
complete. A list containing a variety of open problems is also given.


Comment #2 to TR96-039 | 14th March 1997 09:44

The Complexity of Unary Knapsack with Signed Repetition Comment on: TR96-039





Comment #2 Authors: Holger Petersen
Accepted on: 14th March 1997 09:44
Downloads: 2481
Keywords: 


Abstract:

We prove that the problem is in AC^0.



ISSN 1433-8092 | Imprint