Multi-layer threshold logic function question

[bill@baku.eece.unm.edu]

Does anybody know of bounds on the number of hidden layer units
required to implement an arbitrary logic function over n variables in
a one-hidden layer MLP where each node uses hard-limiting nonlinearities?

Obviously, 2^n is a upper bound:  You can form each possible
conjunction of n variables in the hidden layer, and then selectively
combine them disjunctively with the output node.

This seems like overkill though....  I've seen some other bounds in
Muroga's book which allow for multiple layers and they are on the
order of O(2^(n/2)), but I'm looking specifically for a bound for a
one-hidden layer net.

-Bill

===============================================================================
Bill Horne                                  | email: bill at baku.eece.unm.edu
Dept. of Electical and Computer Engineering |
University of New Mexico                    | Phone:   (505) 277-0805
Albuquerque, NM  87131  USA                 | Office:  EECE  224D
===============================================================================