Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits

Abstract

We discuss a nondeterministic variant of the recently introduced machine model of deterministic auxiliary depth-$k$ storage automata (or aux-$k$-sda's) by Yamakami. It was proven that all languages recognized by polynomial-time logarithmic-space aux-$k$-sda's are located between $\mathrm{LOGDCFL}$ and ${\mathrm{SC}}^k$ (the $k$th level of Steve's class SC). We further propose a new and simple computational model of semi-unbounded fan-in Boolean circuits composed partly of cascading blocks, in which the first few AND gates of unbounded fan-out (called AND${}_{(\ddot{I}‰)}$ gates) at each layer from the left (where all gates at each layer are indexed from left to right) are linked in a "cascading" manner to their right neighbors though specific AND and OR gates. We use this new circuit model to characterize a nondeterministic variant of the aux-$2k$-sda's (called aux-$2k$-sna's) that run in polynomial time using logarithmic work space. By relaxing the requirement for cascading circuits, we also demonstrate how such cascading circuit families characterize the complexity class $\mathrm{P}$. This yields an upper bound on the computational complexity of $\mathrm{LOG}k\mathrm{SNA}$ by $\mathrm{P}$.

(A4, 10pt, 27 pages) This current article extends and corrects its preliminary report that has appeared in the Proceedings of the 28th International Computing and Combinatorics Conference (COCOON 2022), Shenzhen, China, October 22-24, 2022, Lecture Notes in Computer Science, vol. 13595, pp. 61--69, Springer, 2022. The conference talk was given online because of the coronavirus pandemic