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).
BACK