Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cwjcc!tut.cis.ohio-state.edu!ucbvax!pasteur!icsib6!ahmad
From: ahmad@icsib6.Berkeley.EDU (Subutai Ahmad)
Newsgroups: comp.ai.neural-nets
Subject: Re: Minimum # of internal nodes to form boolean function
Message-ID: <18276@pasteur.Berkeley.EDU>
Date: 12 Oct 89 16:27:13 GMT
References: <1989Oct12.050402.9790@boingo.med.jhu.edu>
Sender: news@pasteur.Berkeley.EDU
Reply-To: ahmad@icsi.Berkeley.edu (Subutai Ahmad)
Distribution: usa
Organization: International Computer Science Institute, Berkeley
Lines: 24

In article <1989Oct12.050402.9790@boingo.med.jhu.edu>,
dave@boingo.med.jhu.edu (David Heath) writes:
> 
>   I've been told that Robert Heicht Neilson recently proved that any
> boolean function of n inputs to n outputs can be realized with a neural
> net having n input nodes, n output nodes and 2n-1 intermediate nodes
> (a total of 3 layers). Is there any truth to this statement? 


What transfer functions does he allow? Although it is true that any boolean
function can be realized with 3 layers, it was shown [1] that you
need _at least_ O(2^n/n^2) linear threshold units to implement an 
arbritrary boolean function.  (Note that this result is for n-input 
to 1 output functions but this is at least as difficult as the n-input
to n-output case.)  It is quite feasible that with higher order units 
you can bring this down by a polynomial amount but I doubt that you can 
make much of a difference to the exponential.

Subutai Ahmad
International Computer Science Institute
ahmad@icsi.berkeley.edu

[1] Volper, D.J. and Hampson, S.E.  Connectionist Models of Boolean 
Category Representation. Biological Cybernetics, #54, pp 393-406, 1986.