Search

In this paper, we consider the following problem: given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomia time algorithms.

Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and, therefore, they sometimes hide the essential properties which insure the obtained results. In order to obtain more general results, a uniform family of computation models which encompasses most of the complexity classes of interest is introduced. As a first initial set of results derivable from the proposed approach, we will give a sufficient and necessary condition for proving separations of relativized complexity classes, a characterization of complexity classes with complete languages and a sufficient condition for proving strong separations of relativized complexity classes. Examples of applications of these results to some specific complexity classes are then given. Additional results related to separations by sparse oracles can be found in Bovet (1991).

Complexity classes are usually defined by referring to computation models and by putting suitable restrictions on them. Following this approach, many proofs of results are tightly bound to the characteristics of the computation model and of its restrictions and therefore they sometimes hide the essential properties which ensure the obtained results. In order to obtain more general results, a uniform family of computation models which encompass most of the complexity classes of interest has been introduced in an earlier paper. As an initial set of results derivable from the proposed approach, a necessary and sufficient condition to prove the separation of relativized complexity classes, a characterization of complexity classes which admit a complete language, and a sufficient condition to prove the strong separation of relativized complexity classes have been presented in that paper. In this paper, we apply this approach to obtain positive relativization results, that is, results similar to those obtained in the literature. In particular, our goal is to prove statements of the kind: "Given two complexity classes C and D, C = D if and only if for every sparse set S, CS = DS." We derive a sufficient condition to prove such results and, as an application, we prove a general theorem from which all of the results obtained previously and new ones can be immediately derived.