A Relationship between the Number of Negations and the Circuit Size
Summary :
We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.
- Publication
- IEICE TRANSACTIONS on Information Vol.E79-D No.9 pp.1355-1357
- Publication Date
- 1996/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Keisuke TANAKA, Tetsuro NISHINO, "A Relationship between the Number of Negations and the Circuit Size" in IEICE TRANSACTIONS on Information,
vol. E79-D, no. 9, pp. 1355-1357, September 1996, doi: .
Abstract: We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.
URL: https://global.ieice.org/en_transactions/information/10.1587/e79-d_9_1355/_p
Copy
@ARTICLE{e79-d_9_1355,
author={Keisuke TANAKA, Tetsuro NISHINO, },
journal={IEICE TRANSACTIONS on Information},
title={A Relationship between the Number of Negations and the Circuit Size},
year={1996},
volume={E79-D},
number={9},
pages={1355-1357},
abstract={We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - A Relationship between the Number of Negations and the Circuit Size
T2 - IEICE TRANSACTIONS on Information
SP - 1355
EP - 1357
AU - Keisuke TANAKA
AU - Tetsuro NISHINO
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E79-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1996
AB - We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function Hn, and show that there exists an integer t, which can range over only two different values, such that the removal of one NEGATION gate causes an exponential growth of the optimal circuit size for Hn.
ER -
English
