超二次論理式サイズへ向けた候補となる論理関数

スポンサーリンク

概要

論文の詳細を見る
本論文では,超二次論理式サイズ下界を証明するための可能性と限界について,以下の観点から探究する.まず,再帰的に定義される論理関数を考え,それらに対する一般的な論理式サイズ上界を与える.また,超二次論理式サイズが証明できる可能性のある候補論理関数として,厳密2ビット論理関数を基底として定義される再帰的論理関数を議論する.実際に,その論理式の複雑さが少なくともΩ(n^2)であることを示す.さらに,Karchmer-Wigderson通信ゲームに対する最適なプロトコル分割数の構造から,多数決関数の論理式複雑さを解明することの難しさについて,偶奇判定論理関数と対比しながら考察する.
2012-06-14

著者

関連論文

スポンサーリンク