The Complexity of Computing the Size of an Interval
<|reference_start|>The Complexity of Computing the Size of an Interval: Given a p-order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if (x, y) is an element of 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 polynomial-time computable in the length of x.   By choosing sets of interval size functions based on feasibility requirements for their underlying p-orders, we obtain new characterizations of complexity classes. We prove that the set of all interval size functions whose underlying p-orders are polynomial-time decidable is exactly #P. We show that the interval size functions for orders with polynomial-time 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 polynomial-time 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 polynomial-time decidable partial p-order with polynomial-time 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 polynomial-time decidable total p-order with polynomial-time adjacency checks.   Finally, we explore the related notion of cluster computation.<|reference_end|>
@article{hemaspaandra2005the,
    title={The Complexity of Computing the Size of an Interval},
    author={Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, Klaus W.
  Wagner},
    journal={arXiv preprint arXiv:cs/0502058},
    year={2005},
    number={URCS-TR-2005-856},
    archivePrefix={arXiv},
    eprint={cs/0502058},
    primaryClass={cs.CC cs.DM}
}