Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with component size:
TR04-028 | 19th March 2004
Arfst Nickelsen, Till Tantau, Lorenz Weizs├Ącker

Aggregates with Component Size One Characterize Polynomial Space

Aggregates are a computational model similar to circuits, but the
underlying graph is not necessarily acyclic. Logspace-uniform
polynomial-size aggregates decide exactly the languages in PSPACE;
without uniformity condition they decide the languages in
PSPACE/poly. As a measure of similarity to boolean circuits we
introduce the parameter component size. We ... more >>>

ISSN 1433-8092 | Imprint