論理式サイズ下界に対する長方形限界障壁の突破
スポンサーリンク
概要
- 論文の詳細を見る
Karchmer,Kushilevitz and Nisanは、論理式サイズに関する問題を長方形限界と呼ばれる整数計画問題として定式化し、その線形計画緩和の双対問題に対して実行可能解を与えることで論理式サイズ下界を示す線形計画限界と呼ばれる技術を導入した。線形計画限界の拡張として、本研究では擬加法的限界とSherali-Adams限界と名付けられた論理式サイズ下界を証明する新しい一般的技術を導入する。Sherali-Adams限界は潜在的に長方形限界と等価な下界を示すことが可能な強さを秘めている一方で、擬加法的限界においては長方形限界を上回ることができることを示す。また、万能関係と呼ばれる行列に対する擬加法的限界の解から任意の論理関数に対して論理式サイズ下界を導出できることから、その最適下限に向けて万能関係の構造を議論する。
- 2009-10-09
著者
関連論文
- 論理式サイズ下界に対する長方形限界障壁の突破
- 単調自己双対論理関数の論理式サイズ下限の改良
- 単調自己双対論理関数の論理式サイズ下限の改良
- L versus PのReversal versus Accessへの還元
- 関数の時間、領域計算量について
- 関数の時間、領域計算量について
- 超二次論理式サイズへ向けた候補となる論理関数
- 計算複雑さへの招待(3) : 数理計画法から攻める計算限界