- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Automatic Translation feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
On Sensitivity, Block Sensitivity and Certificate Complexity of Boolean Functions
-
- AMOU Kensaku
- Department of Communications and Systems University of Electro-Communications
-
- TARUI Jun
- Department of Communications and Systems University of Electro-Communications
Bibliographic Information
- Other Title
-
- ブール関数の sensitivity, block sensitivity, certificate complexity について
Search this article
Description
We establishe some relations among sensitivity, block sensitivity, and certificate complexity of Boolean functions. We show that for any Boolean function of n variables, if its sensitivity is s≥2 and its certificate complexity is c, then c≤2^<s-1>s-1 holds. Also, we prove that if a Boolean function of n variables with sensitivity s and certificate complexity c exists, then for any s′ and c′ satisfying s≤s′≤c′≤c, a Boolean function of n variables with sensitivity s' and certificate complexity c′ exists. From the relations we obtain, for n≤7 we can determine the combinations (n, s, c) for which a Boolean function of n variables with sensitivity s and certificate complexity c exists.
Journal
-
- IEICE technical report. Theoretical foundations of Computing
-
IEICE technical report. Theoretical foundations of Computing 97 (628), 93-100, 1998-03-24
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1570572702400056832
-
- NII Article ID
- 110003191371
-
- NII Book ID
- AN10013152
-
- Text Lang
- ja
-
- Data Source
-
- CiNii Articles
