Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-028 | 19th March 2004 00:00

Aggregates with Component Size One Characterize Polynomial Space

RSS-Feed




TR04-028
Authors: Arfst Nickelsen, Till Tantau, Lorenz Weizs├Ącker
Publication: 9th April 2004 21:18
Downloads: 1512
Keywords: 


Abstract:

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 prove that
already aggregates of component size 1
are powerful enough to capture polynomial space.
The only type of cyclic components needed to make polynomial-size
circuits as powerful as polynomial-size aggregates are binary
xor-gates whose output is fed back to the gate as one of the inputs.



ISSN 1433-8092 | Imprint