PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- 1 March 1991
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 2 (1) , 67-76
- https://doi.org/10.1142/s0129054191000054
Abstract
We discuss the relationship between constant-width branching programs and a hierarchy of languages lying between P and PSPACE. We introduce a notion of serializability. A computation is -serializable if it can be organized into a sequence of local computations, c1, c2,…, cr, each of limited power (imposed by the complexity class ), each passing only a few bits of information (a bottleneck) as the result of its computation to the next local computation. By an application of Barrington’s method on branching programs we show that PSPACE is LOGSPACE-serializable with a constant-width bottleneck.Keywords
This publication has 0 references indexed in Scilit: