ECCC-Report TR03-018https://eccc.weizmann.ac.il/report/2003/018Comments and Revisions published for TR03-018en-usMon, 31 Mar 2003 16:01:57 +0300
Paper TR03-018
| Functions Computable in Polynomial Space |
Matthias Galota,
Heribert Vollmer
https://eccc.weizmann.ac.il/report/2003/018We 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.
Mon, 31 Mar 2003 16:01:57 +0300https://eccc.weizmann.ac.il/report/2003/018