𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The number of Boolean functions computed by formulas of a given size

✍ Scribed by Petr Savický; Alan R. Woods

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
323 KB
Volume
13
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Estimates are given of the number B n, L of distinct functions computed by propositional formulas of size L in n variables, constructed using only literals and n, k Ž connectives. L is the number of occurrences of variables. L y 1 is the number of binary ns Ž . and ks. B n, L is also the number of functions computed by two terminal series-parallel . networks with L switches. Enroute the read-once functions, which are closely related to Ž . Ž . L Ž . Schroder numbers, are enumerated. Writing B n, L s b n, L , we find that if L and ␤ n ¨n ␤ Ž n.

Ž

. Ž . go to infinity with increasing n and L F 2 rn , then b n, L ; cn, where c s 2r ln4 y 1 . Making a comparison with polynomial size Boolean circuits, this implies the following. For any constant ␣ ) 1, almost all Boolean functions with formula complexity at most n ␣ cannot be computed by any circuit constructed from literals and fewer than ␣ y1 n ␣ two-input n, k gates.

📜 SIMILAR VOLUMES

The number of labeled graphs placeable b
The number of labeled graphs placeable by a given permutation
✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 370 KB 👁 1 views

Let S be a finite set and u a permutation on S. The permutation u\* on the set of 2-subsets of S is naturally induced by u. Suppose G is a graph and V(G), €(G) are the vertex set, the edge set, respectively. Let V(G) = S. If €(G) and u\*(€(G)), the image of €(G) by u\*, have no common element, then