The complexity of problems in systems of communicating sequential processes

摘要

We examine the complexity of solving certain problems, like the lockout problem, in systems of communicating processes. We restrict our attention to a model where the processes are finite state and where the communication mechanism is that of “shaking hands.” Because the lockout problem is equivalent to the problem of determining whether a player has a winning strategy in a certain kind of game, it can be shown that solving the lockout problem requires exponential time.