Speaker: David Barrington
<br>
<br>
Title: "Functions Computable in Polynomial Space"
<br>
<br>
(by Matthias Galota and Heribert Vollmer)
<br>
<br>
Complexity classes are usually defined as sets of
languages, i.e., sets of functions from strings to
{0,1}.  We also sometimes want to talk about sets of
functions from strings to the non-negative integers N
or the integers Z.  For example #P is the set of functions
f_M where f_M(x) is the number of accepting paths of some
poly-time nondeterministic Turing machine M on input x.
This paper presents several characterizations of the class
FPSPACE, of functions from strings to Z where the binary
representation of f(x) can be computed from x in polynomial
space.
<br>
<br>
Many of the results in the paper use an interesting
generalization of nondeterminism called the _leaf language
formalism_.  Given a poly-time NDTM and an input, consider
the exponential-size tree of possible computation, view the
sequence of results at the leaves of this tree (in order)
as a string, and test this string for membership in some
language.  (For example, the input is in the language of the
NDTM iff this leaf string is in {0,1}^*1{0,1}^*.)  This
formalism unifies the relationship between low-level classes
on the one hand and classes between P and PSPACE on the other.
<br>
<br>
I'll give an introduction to both function classes and the
leaf language formalism and then present some of the results
of the paper.  The entire paper is available on-line as ECCC
report TR03-018 from the eccc.uni-trier.de site.