Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950746 | Information and Computation | 2016 | 11 Pages |
Abstract
As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators is in deterministic SPACE(log2â¡n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE(nlogâ¡n); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(n).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anna Gál, Jing-Tang Jang,