Universally Serializable Computation

摘要

Cai and Furst proved that every PSPACE language can be solved via a large number of identical simple tasks, each of which is provided with the original input, its own unique task number, and at most three bits of output from the previous task. In the Cai–Furst model, the tasks are required to be run in the order specified by the task numbers. To study the extent to which the Cai–Furst PSPACE result is due to this strict scheduling, we remove their ordering restriction, allowing tasks to execute in any serial order. That is, we study the extent to which complex tasks can be decomposed into large numbers of simple tasks that can be scheduled arbitrarily. We provide upper bounds on the complexity of the sets thus accepted. Our bounds suggest that Cai and Furst's surprising PSPACE result is due in large part to the fixed order of their task execution. In fact, our bounds suggest the possibility that even relatively low levels of the polynomial hierarchy cannot be accepted via large numbers of simple tasks that can be scheduled arbitrarily. However, adding randomization recaptures the polynomial hierarchy. The entire polynomial hierarchy can be accepted by large numbers of arbitrarily scheduled probabilistic tasks passing only a single bit of information between successive tasks (and using J. Simon's “exact counting” acceptance mechanism). In fact, we show that the class of languages so accepted is exactly NPPP.