SYMPOSIUM MINISYMPOSIA

ABSTRACT

Computations of a non-deterministic Turing machine (NTM) can be represented by trees. Early on it was noted that in most cases we can restrict computation trees to binary trees without loss of generality w.r.t. the computational power. Recently the trend has been to study the influence of even more detailed structural properties of (binary) computation trees (e.g. whether complete, balanced, etc.). An important question in this context is whether the computational power of a complexity class decreases if only computation trees belonging to a special family are allowed.

Hertrampf, Vollmer and Wagner defined the class Path which is based on the value of the i-th path of a NTM. Path is supposedly a class much higher than P. In their paper it is stated that if the definition of the class Path were restricted only to balanced computation trees the corresponding complexity class would be lower than P. Path has an "irregular" behavior, since most known complexity classes remain invariant under similar "reasonable" definitional restrictions. For example NP, #P, PP possess the same computational power even if we restrict shapes of computation trees to complete binary.

In this paper we emphasize that such "irregular" behavior is related to the fact that both accepting and rejecting paths are important for determining the outcome of the computation. This is the reason that, in particular, complexity classes whose definition involves order of paths have such behavior: indeed determining the order of a path in a general tree may be difficult whereas in the case of a regular tree (e.g. complete or balanced) it is easy.

To demonstrate the power of determining path order, we introduce three functionclasses, RAP, LAP and MAP, which differ from their restricted versions unless the polynomial hierarchy collapses. These classes are closely related to other well-known complexity classes. We also present TotP, a class of functions that output the total number of paths (rejecting plus accepting) This class is proved to be equally powerfull to #P when used as an oracle; the same holds for all our classes: P ^RAP = P ^LAP = P ^MAP = P ^TotP = P ^#P.

We also introduce the concept of class-shape, in order to provide a formal framework for investigating complexity classes whose possible computation trees are restricted. If a family of trees S is sufficient to describe all computations of all members of a class C, then we say that S is a sufficient shape for C. We focus on the family of complete binary trees (CBT) that turns out to be a sufficient shape for many known complexity classes but not for our path-order classes (unless PH collapses). Some CBT-restricted versions of our new classes are closely related to classes of optimization problems. Thus, for example, we provide an alternative description for Krentel's OptP and Toda's MidP classes. Finally our path-order classes are natural extensions of the classes max-P and min-P defined by Hempel and Wechsung and M_ed P defined by Vollmer and Wagner.

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu