Abstract:

Given a porder A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if
(x, y) ∈ A then x is polynomially bounded by y), an interval size function of A returns, for each string
x in the universe, the number of strings in the interval between strings b(x) and t(x) (with respect to A),
where b(x) and t(x) are functions that are polynomialtime computable in the length of x.
By choosing sets of interval size functions based on feasibility requirements for their underlying porders,
we obtain new characterizations of complexity classes. We prove that the set of all interval size functions
whose underlying porders are polynomialtime decidable is exactly #P. We show that the interval size
functions for orders with polynomialtime adjacency checks are closely related to the class FPSPACE(poly).
Indeed, FPSPACE(poly) is exactly the class of all nonnegative functions that are an interval size function
minus a polynomialtime computable function.
We study two important functions in relation to interval size functions. The function #DIV maps
each natural number n to the number of nontrivial divisors of n. We show that #DIV is an interval
size function of a polynomialtime decidable partial porder with polynomialtime adjacency checks. The
function #MONSAT maps each monotone boolean formula F to the number of satisfying assignments of
F. We show that #MONSAT is an interval size function of a polynomialtime decidable total porder with
polynomialtime adjacency checks.
Finally, we explore the related notion of cluster computation. 