2014 · 38 citations · 23 references
ComputingComputer ScienceAlgorithmsCatalysisTheory Of ComputationCircuit ComplexityComputational ComplexityMatrix ComputationSpace ComplexityLogarithmic SpaceLogarithmic Space ComplexityMemory-bounded AlgorithmsSpace-bounded Computation
We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform TC1-circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. TC1-circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace.
23
Logical Reversibility of Computation
C. H. Bennett · IBM Journal of Research and Development · 1973 · 3.7K citations
Completeness classes in algebra
Leslie G. Valiant · 1979 · 487 citations · Full text