A Relationship between the Number of Negations and the Circuit Size
スポンサーリンク
概要
- 論文の詳細を見る
We show a relationship between the number of negations in circuits and the size of circuits. More precisely, we construct a Boolean function H_n, 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 H_n.
- 一般社団法人電子情報通信学会の論文
- 1996-09-25
著者
-
Nishino Tetsuro
Department Of Communications And Systems Engineering The University Of Electro-communications
-
Nishino Tetsuro
Department Of Communications And Systems Engineering University Of Electro-communications
-
Tanaka Keisuke
School of Information Science, Japan Advanced Institute of Science and Technology
-
Tanaka Keisuke
School Of Information Science Japan Advanced Institute Of Science And Technology
関連論文
- On the Negation-Limited Circuit Complexity of Clique Functions
- Single Machine Scheduling to Minimize the Maximum Lateness with Both Specific and Generalized Due Dates (Special Section of Selected Papers from the 9th Karuizawa Workshop on Circuits and Systems)
- Approximation algorithms for scheduling problems with generalized due dates
- Lower bounds of the negation-limited circuit complexity
- The Complexity of Threshold Circuits for Parity Functions
- A Relationship between the Number of Negations and the Circuit Size
- An Introduction to Quantum Complexity Theory (第6回『非平衡系の統計物理』シンポジウム)