Computing in Logarithmic Space
The set logspace, of logarithmic space computable string functions is defined. It is easily seen that logspace ≤ polytime, the set of polynomial time computable functions. ogspace is shown to equal L, the smallest class of recursive string functions containing concatenation and the equality function...
Main Author: | Lind, John C. |
---|---|
Published: |
2023
|
Online Access: | https://hdl.handle.net/1721.1/148880 |
Similar Items
-
Unification and Logarithmic Space
by: Clément Aubert, et al.
Published: (2018-07-01) -
From normal functors to logarithmic space queries
by: Nguyên, L, et al.
Published: (2019) -
Logarithmic SAT Solution with Membrane Computing
by: Radu Nicolescu, et al.
Published: (2022-02-01) -
Quantum computation of discrete logarithms in semigroups
by: Childs Andrew M., et al.
Published: (2014-12-01) -
Efficient architectures for computation of binary logarithm
by: Low, Joshua Yung Lih
Published: (2014)