論理式サイズ下界に対する長方形限界障壁の突破 Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds

Karchmer,Kushilevitz and Nisanは、論理式サイズに関する問題を長方形限界と呼ばれる整数計画問題として定式化し、その線形計画緩和の双対問題に対して実行可能解を与えることで論理式サイズ下界を示す線形計画限界と呼ばれる技術を導入した。線形計画限界の拡張として、本研究では擬加法的限界とSherali-Adams限界と名付けられた論理式サイズ下界を証明する新しい一般的技術を導入する。Sherali-Adams限界は潜在的に長方形限界と等価な下界を示すことが可能な強さを秘めている一方で、擬加法的限界においては長方形限界を上回ることができることを示す。また、万能関係と呼ばれる行列に対する擬加法的限界の解から任意の論理関数に対して論理式サイズ下界を導出できることから、その最適下限に向けて万能関係の構造を議論する。

Karchmer, Kushilevitz and Nisan formulated the formula size problem as an integer programming problem called the rectangle bound and introduced a technique called the LP bound, which gives a formula size lower bound by showing a feasible solution of the dual problem of its LP-relaxation. As extensions of the LP bound, we introduce novel general techniques proving formula size lower bounds, named as a quasi-additive bound and the Sherali-Adams bound. While the Sherali-Adams bound is potentially strong enough to give a lower bound matching to the rectangle bound, we prove that the quasi-additive bound can surpass the rectangle bound. We also discuss structure of the universal relation towards its matching bound because we can derive a formula size lower bound of any Boolean function from a solution of the quasi-additive bound for the universal relation.