UNIVERSALLY SERIALIZABLE COMPUTATION

LANE A. HEMASPAANDRA? AND MITSUNORI OGIHARAy

Abstract. Cai and Furst [7] 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.

Key words. structural complexity theory, safe storage machines, bottleneck machines

AMS subject classifications. 68Q15, 03D15

1. Introduction

A key theme in modern computer science is the decomposition of a complex task into a number of smaller, simpler, tasks. Though this is often studied in the context of parallel computation, Cai and Furst [7] investigate this issue in terms of serial computation. They propose a model in which a given computation is decomposed into an exponential number of polynomial-time tasks that are identical except in that each is given, in addition to the problem input, its own unique task number plus a few bits of output allowed to be passed on from the previous task. The computation accepts" if the final task outputs some particular value (e.g., 1"). Building on Barrington's [1] seminal work on branching programs, Cai and Furst prove that every PSPACE language can be accepted in this way, even if the tasks run in logarithmic space rather than in polynomial time. Keeping in mind that Cai and Furst additionally require the tasks to be executed in the lexicographical order of their task numbers, and indeed use the term clock" in place of what here is called a task number, let us

? Department of Computer Science, University of Rochester, Rochester, NY 14627. Supported in part by grants NSF-CCR-8957604, NSF-INT-9116781/JSPS-ENGR-207, and NSF-CCR-9322513. Work done in part while visiting the Tokyo Institute of Technology. Email: lane@cs.rochester.edu.
y Department of Computer Science, University of Rochester, Rochester, NY 14627. Supported in part by grant NSF-INT-9116781/JSPS-ENGR-207. Email: ogihara@cs.rochester.edu.