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

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

Aggregates are a computational model similar to circuits, but the

underlying graph is not necessarily acyclic. Logspace-uniform

polynomial-size aggregates decide exactly the languages in PSPACE;

without uniformity condition they decide the languages in

PSPACE/poly. As a measure of similarity to boolean circuits we

introduce the parameter component size. We ...
more >>>