ブール関数の sensitivity, block sensitivity, certificate complexity について
書誌事項
- タイトル別名
-
- On Sensitivity, Block Sensitivity and Certificate Complexity of Boolean Functions
この論文をさがす
説明
本論文では、ブール関数のsensitivity, block sensitivity, certificate complexity に関して成立する関係をいくつか示す。任意のn変数ブール関数のsensitivity s≥2とcertificate complexity c についてc≤2^<s-1>s-1が成立することを示す。また、sensitivity s, certificate complexity cの n変数ブールが存在すれば、s≤S′≤c′≤cを満たす任意のsとcについて、sensitivity s′, certificate complexity c′のn変数ブール関数が存在することを示す。得られた関係により、n≤7の場合の(n, s, c)のとりうる値を完全に決定することができる。
収録刊行物
-
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
-
電子情報通信学会技術研究報告. COMP, コンピュテーション 97 (628), 93-100, 1998-03-24
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570572702400056832
-
- NII論文ID
- 110003191371
-
- NII書誌ID
- AN10013152
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles
