๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Universally Serializable Computation

โœ Scribed by Lane A. Hemaspaandra; Mitsunori Ogihara


Book ID
102585819
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
371 KB
Volume
55
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis


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 NP PP .


๐Ÿ“œ SIMILAR VOLUMES


On serializability
โœ J. A. Brzozowski; S. Muro ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Springer ๐ŸŒ English โš– 742 KB
On serializability
โœ J.A. Brzozowski; S. Muro ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 62 KB
cover
โœ Bell, Anna ๐Ÿ“‚ Fiction ๐Ÿ“… 2014 ๐ŸŒ English โš– 150 KB ๐Ÿ‘ 2 views