StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

Eric Allender; Klaus-Joern Lange

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR96-048 | 12th September 1996 00:00

StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

TR96-048 Authors: Eric Allender, Klaus-Joern Lange
Publication: 13th September 1996 19:47
Downloads: 2235

Keywords:

Parallel Pointer Machines, PRAMs, space complexity, Unambiguity

Abstract:

We present a deterministic algorithm running in space
O((log^2 n)/loglog n) solving the connectivity problem
on strongly unambiguous graphs. In addition, we present
an O(log n) time-bounded algorithm for this problem
running on a parallel pointer machine.

ISSN 1433-8092 | Imprint