On the Negation-Limited Circuit Complexity of Clique Functions
スポンサーリンク
概要
- 論文の詳細を見る
A negation-limited circuit is a combinational circuit which includes at most 「log(n+1)」 NOT gates. We show a relationship between the size of negation-limited circuits computing clique functions and the number of NOT gates in the circuits.
- 社団法人電子情報通信学会の論文
- 1995-01-25
著者
-
Nishino Tetsuro
School Of Information Science Japan Advanced Institute Of Science And Technology
-
Tanaka K
Univ. Kagoshima Kagoshima‐shi Jpn
-
Tanaka Keisuke
School of Information Science, Japan Advanced Institute of Science and Technology
-
Tanaka K
Tokyo Inst. Of Technol. Tokyo Jpn
-
Tanaka Keisuke
School Of Information Science Japan Advanced Institute Of Science And Technology
関連論文
- Data Hidng under Fractal Image Generation via Fourier Filtering Method
- Data Hiding via Steganographic Image Transformation(Special Section on Intelligent Signal and Image Processing)
- 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
- Abstraction and Inheritance of HyperLinks in an Object-Oriented Hypertext Database System TextLink/Gem
- The Emptiness Problem for Lexical-Functional Grammars is Undecidable
- Lower bounds of the negation-limited circuit complexity
- A Relationship between the Number of Negations and the Circuit Size
- A Simulation Result for Simultaneously Bounded AuxPDAs
- On the Number of Negations Needed to Compute Parity Functions