Abstract
Based on explicit numerical constructions for Kolmogorov's superpositions (KS) linear size circuits are possible. Because classical Boolean as well as threshold logic implementations require exponential size in the worst case, it follows that size-optimal solutions for arbitrary Boolean functions (BFs) should rely (at least partly) on KS. In this paper, we will present previous theoretical results while examining the particular case of 3-input BFs in detail. This shows that there is still room for improvement on the synthesis of BFs. Such size reductions (which can be achieved systematically) could help alleviate the challenging power consumption problem, and advocate for the design of Kolmogorov-inspired gates, as well as for the development of the theory, the algorithms, and the CAD tools that would allow taking advantage of such optimal combinations of different logic styles.
Original language | English |
---|---|
Pages (from-to) | 438-445 |
Number of pages | 8 |
Journal | Lecture Notes in Computer Science |
Volume | 3512 |
DOIs | |
Publication status | Published - 2005 |
Event | 8th International Workshop on Artificial Neural Networks, IWANN 2005: Computational Intelligence and Bioinspired Systems - Vilanova i la Geltru, Spain Duration: Jun 8 2005 → Jun 10 2005 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)