TR03-018 Authors: Matthias Galota, Heribert Vollmer

Publication: 31st March 2003 16:01

Downloads: 1450

Keywords:

We show that the class of integer-valued functions computable by

polynomial-space Turing machines is exactly the class of functions f

for which there is a nondeterministic polynomial-time Turing

machine with a certain order on its paths that on input x outputs a 3x3

matrix with entries from {-1,0,1} on each path such that f(x) is exactly

the upper left entry in the product of all these matrices in the order of

the paths. Along the way we obtain characterizations of FPSPACE in terms

of arithmetic circuits and straight-line programs.