𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In

✍ Scribed by György Turán; Farrokh Vatan

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
741 KB
Volume
54
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the complexity of computing Boolean functions by analog circuits of bounded fan-in, i.e., by circuits of gates computing real-valued functions, either exactly or as sign-representation. Sharp upper bounds are obtained for the complexity of the most difficult n-variable function over certain bases (sign-representation by arithmetic circuits and exact computation by piecewise linear circuits). Bounds are given for the computational power gained by adding discontinuous gate functions and nondeterminism. We also prove explicit nonlinear lower bounds for the formula size of analog circuits over bases containing addition, subtraction, multiplication, the sign function and all real constants.

📜 SIMILAR VOLUMES

The number of Boolean functions computed
The number of Boolean functions computed by formulas of a given size
✍ Petr Savický; Alan R. Woods 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 323 KB 👁 2 views

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 f

Bounds on the number of Hamiltonian circ
Bounds on the number of Hamiltonian circuits in the n-cube
✍ Robert James Douglas 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 224 KB

New upper anti lower ~,ounds arc found for the number of HamilI(,nian circuits in the graph of Ihe r -cube. (2) -1 i,, ,,' We show that h(n)~ [n(n -I)/212 .... '~'"""',"' = U~(e,) (3)

On the Factorization of Functions Bounde
On the Factorization of Functions Bounded and Analytic in a Half Plane
✍ Rolf Scharm 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 453 KB 👁 1 views

We consider functions f l , fa analytic in the upper half plane and continuous in its closure and investigate the following problem: Suppose that the product flfa is bounded in the half plane and both factors are bounded on the real axis; which assumptions on the growth of fl are sufficient for fz