The Complexity of Computing the Size of an Interval

Details The Complexity of Computing the Size of an Interval The Complexity of Computing the Size of an Interval

2005-02-13

arxiv.org/abs/cs/0502058v2

Computer Science

Computational Complexity

This revision fixes a problem in the proof of Theorem 9.6

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Computing the Size of an Interval does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Computing the Size of an Interval, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Computing the Size of an Interval will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-674333