All reports by Author Matthias Galota:

__
TR03-018
| 28th March 2003
__

Matthias Galota, Heribert Vollmer#### Functions Computable in Polynomial Space

Matthias Galota, Heribert Vollmer

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 ...
more >>>