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?

  • 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 Sep 25 '17 at 9:45
  • 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). 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 Sep 25 '17 at 15:10
  • 4
    It’s easy to find LogCFL-complete problems in the literature. In particular, 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 Sep 25 '17 at 15:20
  • @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 Sep 25 '17 at 16:22

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.