<p>The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, because the wiring could destroy the theoretical speed benefits.</p>

<p>A more promising approach could be to look for problems complete under appropriate many-one reductions for these classes. The word problem for $\bar{A}_5$ (or $\bar{S}_5$) would be such a problem for $NC^1$. The solution of that word problem is nicely scalable, since one can subdivide the word into smaller parts, and thereby generate a smaller word on which the same procedure can be applied again.</p>

<p>Is something similar also possible for LogCFL ($= sAC^1$)? Does it have a nice problem (probably some CFL) complete under $NC^1$ reductions? And is the solution of that CFL scalable in a way that hardware solutions to subproblems can easily be combined to the total solution?</p>

<p>Or does the dynamic programming algorithm which can solve LogCFL allows scalable hardware support in some way?</p>

CC BY-SA 3.0
2017-09-25T09:45:28.870Z
One clear subquestion is whether there are reasonable problems/languages LogCFL-complete under $NC^1$ reductions. My current research of that subquestion was not successful yet. But there may be other ways to provide scalable hardware support for LogCFL, hence my question is a bit open ended.
Thomas Klimpel
CC BY-SA 3.0
2017-09-25T15:10:30.310Z
I can’t say I understand what you mean by “scalable” (only that it seems to be something much more restricted than [its usual meaning](https://en.wikipedia.org/wiki/Scalability)). But you certainly cannot expect LogCFL-complete problems to have the property that any instance can be solved by using solutions to a constant number of subproblems whose size is at most a constant fraction of the original input size, as any such problem is in (nonuniform) NC^1.
Emil Jeřábek
CC BY-SA 3.0
2017-09-25T15:20:59.470Z
It’s easy to find LogCFL-complete problems in the literature. In particular, https://arxiv.org/abs/cs/9809114 prove that Greibach’s “hardest CFL” equipped with a padding symbol is LogCFL-complete under a subclass of $\mathrm{AC}^0$ reductions.
Emil Jeřábek
CC BY-SA 3.0
2017-09-25T16:22:09.297Z
@EmilJeřábek Very good, my inital hopes were a language along those lines. I mean "scalable" compared to a pure hardware implementation: If the sAC^1 circuit for the LogCFL-complete language would be implemented entirely in hardware (for a given input length), then its depth and size would scale "nicely". What I am interested in is a large but fixed size hardware, whose solutions can be combined together, as easy or as complicated as expected for sAC^1.
Thomas Klimpel
<cc.complexity-theory><space-bounded><context-free><dynamic-programming>
Is scalable hardware support for LogCFL (= sAC^1) possible?
Thomas Klimpel
# Is scalable hardware support for LogCFL (= sAC^1) possible?

(Asked by: username_0 on 2017-09-24)

The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, because the wiring could destroy the theoretical speed benefits.

A more promising approach could be to look for problems complete under appropriate many-one reductions for these classes. The word problem for $\bar{A}\_5$ (or $\bar{S}\_5$) would be such a problem for $NC^1$. The solution of that word problem is nicely scalable, since one can subdivide the word into smaller parts, and thereby generate a smaller word on which the same procedure can be applied again.

Is something similar also possible for LogCFL ($= sAC^1$)? Does it have a nice problem (probably some CFL) complete under $NC^1$ reductions? And is the solution of that CFL scalable in a way that hardware solutions to subproblems can easily be combined to the total solution?

Or does the dynamic programming algorithm which can solve LogCFL allows scalable hardware support in some way?

**Tags:** cc.complexity-theory, space-bounded, context-free, dynamic-programming

> **Comments:**
> **username_0**: One clear subquestion is whether there are reasonable problems/languages LogCFL-complete under $NC^1$ reductions. My current research of that subquestion was not successful yet. But there may be other ways to provide scalable hardware support for LogCFL, hence my question is a bit open ended.  
> **username_1**: I can’t say I understand what you mean by “scalable” (only that it seems to be something much more restricted than [its usual meaning](https://en.wikipedia.org/wiki/Scalability)). But you certainly cannot expect LogCFL-complete problems to have the property that any instance can be solved by using solutions to a constant number of subproblems whose size is at most a constant fraction of the original input size, as any such problem is in (nonuniform) NC^1.  
> **username_1**: It’s easy to find LogCFL-complete problems in the literature. In particular, https://arxiv.org/abs/cs/9809114 prove that Greibach’s “hardest CFL” equipped with a padding symbol is LogCFL-complete under a subclass of $\mathrm{AC}^0$ reductions.  
> **username_0**: @EmilJeřábek Very good, my inital hopes were a language along those lines. I mean "scalable" compared to a pure hardware implementation: If the sAC^1 circuit for the LogCFL-complete language would be implemented entirely in hardware (for a given input length), then its depth and size would scale "nicely". What I am interested in is a large but fixed size hardware, whose solutions can be combined together, as easy or as complicated as expected for sAC^1.  

---

## 0 answers

