REPORTS > DETAIL:
Paper:
TR96-039 | 27th June 1996 00:00
A Compendium of Problems Complete for Symmetric Logarithmic Space
TR96-039 Authors: Carme Alvarez, Raymond Greenlaw
Publication: 15th July 1996 23:27
Downloads: 135
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
Comment #1 Authors: Carme Alvarez, Raymond Greenlaw
Accepted on: 13th September 1996 16:27
Downloads: 133
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.
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: 133
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
Abstract:
We prove that the problem is in AC^0.
The Complexity of Unary Knapsack with Signed Repetition Comment on: TR96-039
Abstract:
We prove that the problem is in AC^0.