On the computational complexity of behavioral description-based web service composition

The behavioral description-based Web Service Composition (WSC) problem deals with the automatic construction of a coordinator web service that controls a set of web services to reach the goal states. Despite its importance and implications, very few studies exist on the computational complexities of the WSC problem. In this paper, to address this problem, we present four novel theoretical findings on the WSC problem: (1) solving the composition problem of deterministic web services for a restricted case (when the coordinator web service has complete information about the states of all web services) is PSPACE-complete; (2) solving the composition problem of deterministic web services for a general case (when the coordinator web service has incomplete information about the states of web services) is EXPSPACE-complete; (3) solving the composition problem of non-deterministic web services on complete information is EXP-complete and (4) solving the composition problem of non-deterministic web services on incomplete information (which is the most general case) is 2-EXP-complete. These findings suggest that more efforts to devise efficient approximation solutions to the WSC problem is needed.