On the complexity of narrow systems of Boolean functions

We consider the complexity of generating systems of Boolean vectors by circuits. The unit vectors are used as the initial vectors called generators. We investigate the behaviour of the Shannon function of the complexity of systems in the case, where the number of vectors in the systems and the logarithm of their dimension are of the same order, and obtain an asymptotically exact formula for the Shannon function.
The research was supported by the Russian Foundation for Basic Research, grant 96–01–01068, and the Federal Program ‘Integration’, grant 473.