Circuit Complexity Theory

The Computational Capability of Neurel Networks

In the filed of cognitive psychology, the simple recurrent networks are used for modeling the natural language processing in the human brain. For example, Elman confirmed experimentally that simple recurrent networks can predict the rightmost word in sentential forms of a particular context-free grammar with high probability. Concerning these results, it is natural to ask whether the computational capability of the simple recurrent networks is sufficient to recognize natural languages.

First, we adopt the following assumption:

The range of a function computed at each gate of a simple recurrent network is a finite set. This is a quite realistic assumption especially when we perform a computer simulation of a simple recurrent network using current computing devices, because we cannot physically implement a gate whose range is an infinite set. Then, we define equivalence relations between simple recurrent networks and Mealy machines or Moore machines, which are finite automata with output. We show (1) a construction of a Mealy machine which simulates a simple recurrent network, and (2) a construction of simple recurrent networks which simulates Moore machines under our assumption. These two constructions show that the computational capability of the simple recurrent networks is equal to that of finite automata with output under our assumption.

Jyunnosuke Moriya and Tetsuro Nishino : A Comparison of the Computational Capabilities of Simple Recurrent Networks and Finite Automata(in preparation).

Negation-Limited Circuit Complexity

A combinational circuit is a circuit whose basis is AND, OR, and NOT, and a monotone circuit is a circuit whose basis is AND and OR. Let n be the number of inputs for circuits. A negation-limited circuit is a combinational circuit which includes at most (approximately) log n NOT gates. Markov showed that for any Boolean function f with n variables, (approximately) log n NOT gates are sufficient to compute f. By this result, for all Boolean function f, there exists a negation-limited circuit computing f.
Despite some considerable effort encompassing almost 40 years, even a result showing that some explicitly defined family of Boolean functions has superlinear combinational complexity is not known. On the other hand, for monotone circuit model, Razborov gave superpolynomial lower bounds for clique functions. Subsequently, Alon and Boppana improved Razborov’s bounds to exponential. Thus, an interesting approach for superlinear lower bounds on the combinational complexity is the investigation of the complexity of the negation-limited circuits. We proved many fundamental theorems on the negation-limited circuit complexity.

 - Keisuke Tanaka and Tetsuro Nishino : On the Complexity of Negation-Limited Boolean Networks, Proceedings of the 26th ACM Symposium on Theory of Computing, Montreal, Canada, May 23-25, pp.38-47 (1994).

 - Robert Beals, Tetsuro Nishino and Keisuke Tanaka : More on the Complexity of Negation-Limited Circuits, Proceedings of the 27th ACM Symposium on Theory of Computing, Las Vegas, NV, May 29-June 1, pp.585-595 (1995).

 - Tetsuro Nishino and Keisuke Tanaka : On the Negation-Limited Circuit Complexity of Clique Functions, IEICE Transactions on Information and Systems, Vol.E78-D, No.1, pp.86-89 (1995).

 - Keisuke Tanaka, Tetsuro Nishino and Robert Beals : Negation-limited Circuit Complexity of Symmetric Functions, Information Processing Letters, Vol. 59, pp.273-279 (1996).

 - Keisuke Tanaka and Tetsuro Nishino : A Relationship Between tne Number of Negations and the Circuit Size, IEICE Transactions on Information and Systems, Vol. E79-D, No.9 SEPTEMBER 1996, pp.1355-1357.

 - Robert Beals, Tetsuro Nishino and Keisuke Tanaka : On the Complexity of Negation-limited Boolean Networks, SIAM Journal on Computing, Vol. 27, No. 5, pp. 1334-1347 (1998).