単調自己双対論理関数の論理式サイズ下限の改良

スポンサーリンク

概要

論文の詳細を見る
本研究は、Karchmer, Kushilevitz and Nisanによって導入された線形計画限界と安定集合多面体の理論に基づき、論理式サイズの下限を証明する新しい技法を導入する。この新しい技法を多数決関数に適用することで、Khrapchenkoによる古典的結果から論理式サイズの下限を改良する。さらに、単調自己双対論理関数の分解理論からの動機付けにより非平衡再帰3分多数決関数の概念を導入し、それらの論理式サイズの整数的に最適な上限と下限を示す。また、平衡再帰3分多数決関数の単調論理式サイズに対してLaplante, Lee and Szegedyの量子敵対者限界により得られた値より改良された下限を示す。
一般社団法人情報処理学会の論文
2008-11-26

著者

上野賢哉
東京大学大学院情報理工学系研究科コンピュータ科学専攻

関連論文

スポンサーリンク