論理式サイズ下界の証明は,計算理論において最も本質的かつ重要な問題のうちの一つである.多項式サイズの論理式で計算できる言語のクラスはNC1と呼ばれる計算量クラスと等価であるため,例えば,計算量クラスPに属する論理関数に対して,その超多項式下界を証明することでNC1≠Pといった結論が得られる.その証明技術に関しては,古典的な手法であるKhrapchenkoによる1971年の結果をはじめとして長年多くの研究者により研究されてきた一方でその解決には程遠い.

Karchmer, Kushilevitz and Nisanは,論理式サイズ下界の問題から導出されるある整数計画問題として定式化し,それを線形緩和することで得られる定式化の双対問題に対して実行可能解を与えることで論理式サイズ下界を証明する一般的技術,線形計画限界を導入した.近年,この線形計画限界が多くの既存の証明手法を包括することが明らかにされてきた.本論文では,この線形計画限界に対する三通りの方法による拡張版を導入する.

一つ目の方法では,安定集合多面体の理論に基づきクリーク制約式という新しい制約条件を導入することで行われる.この新しい技法を多数決関数に適用することで,Khrapchenkoによる古典的結果から論理式サイズの下界を改良する.さらに,単調自己双対論理関数の分解理論からの動機付けにより非平衡再帰3分多数決関数の概念を導入し,それらの論理式サイズの整数的に最適な上限と下限を示す.また,平衡再帰3分多数決関数の単調論理式サイズに対してLaplante, Lee and Szegedyの量子敵対者限界により得られた値より改良された下界を示す.

二つ目の方法では,体系的に線計画問題の制約条件をきつくする制約式を導入する方法である,Lift-and-Project法を利用する.複数ある方法の中で,その相対的な簡潔さと強力さから本論文ではSherali and Adamsの方法を採用する.この手法により,最終的に整数解の凸包を表現するLP定式化が得られる.したがって,原理的には整数計画問題の最適解と同等の値を証明する能力を秘めた証明手法を提案したことになる.

三つ目の方法では,Hrube{s}, Jukna, Kulikov and Pudl{'a}kにより最近導入された劣加法的長方形尺度という概念から,整数計画問題を介さずに直接に論理式サイズの下界となる線形計画定式化を導入する.この方法では,おおもとの線形計画限界の純粋な拡張でありながら,整数計画問題の最適解を破れることを示す.一般に,整数計画問題の最適解は論理式サイズから大きくは離れていないことから,この結果は新しい技術の強い潜在能力を示唆する.したがって,強い論理式サイズ下界へ向けて有望な方向性を提示するものである.さらに,万能関係と呼ばれる全ての論理関数を包括する数理構造に対して下界を与える解空間を構成することで,任意の論理関数への下界をそのまま得ることができる.本論文では,その最適下界へ向けた解空間の構造を議論する.

論理式サイズ下界の証明は、計算理論の歴史において、その理論の本質に係る最も重要な問題のうちの一つである。その証明手法については、Khrapchenko (1971)により、パリティ関数に対してn2の下界が証明されて以来、多くの努力がなされてきた。なかでも、Karchmer, Kushilevitz, Nisan (1995)らが、論理式サイズ下界問題をrectangle boundと呼ばれる整数計画問題として定式化し、それを線形緩和した問題の双対問題に対して実行可能解を示すことにより論理式サイズの下界を証明するLP bound(線形計画限界)と呼ばれる一般的証明手法を考案したことにより大きな進展が見られた。そして、最近になって、この線形計画限界が多くの既存の証明手法を包括することが明らかにされてきた。本論文は、この線形計画限界を独立の三つの方向に拡張し、論理式サイズの下界を証明するための新たな証明手法を創出したものである。

本論文は次のように構成されている。第1章では、論理式サイズの下界証明問題に対する挑戦の歴史が概観されており、第2章では、問題の定式化と、Kurapuchenko以来、過去40年ほどの間に得られた結果が体系的に解説され、本論文の貢献の位置づけを行っている。第3章はKarchmer, Kushilevitz, Nisan (1995)らの証明手法を紹介し、またその手法の限界について述べている。第4章から第6章において、本論文の主結果である論理式サイズの下界証明手法のための理論が展開されている。

第4章は、安定集合多面体の理論に基づきクリーク制約式という新しい制約条件を導入することにより得られた新たな証明手法について論じている。この証明手法を多数決関数に適用することで,Khrapchenkoによる古典的結果から論理式サイズの下界を改良している。さらに、単調自己双対論理関数の分解理論にヒントを得て、非平衡再帰3分多数決関数の概念を導入し、それらの論理式サイズの最適な上限と下限を証明している。また、平衡再帰3分多数決関数の単調論理式サイズに対して、Laplante, Lee, Szegedy (2006)の量子敵対者限界により得られた値より改良された下界を証明することにも成功している。

第5章は、体系的に線計画問題の制約条件を厳しくする制約式を導入する方法として知られているLift-and-Project法を利用した証明手法について論じている。この手法は、知られている線形緩和方法の中で、その相対的な簡潔さと強力さからSherali, Adams (1990, 1994)の方法を用いたもので、最終的に整数解の凸包を表現するLP定式化を得ている。このため、原理的には整数計画問題の最適解と同等の値を証明する能力を秘めた証明手法となっている。

第6章は、Hrubes, Jukna, Kulikov, Pudlak (2009)により導入された劣加法的長方形尺度(subadditiverectangular measure)という概念から導出される、整数計画問題を介さずに直接に論理式サイズの下界となる線形計画定式化を行ったquasi-additive boundという手法について論じている。この手法の優れている点は、線形計画限界の純粋な拡張でありながら、整数計画問題の最適解を超えられることであり、論理式サイズの下界証明へ向けて、有力な方法になる可能性があることを示唆している。

以上、いずれの結果も深い数学的議論に基づいたもので、Karchmer, Kushilevitz, Nisan (1995)らの線形計画限界による手法を本質的に超えたものである。第7章では、こうした結果を総括し、論理式サイズ下界問題の難しさと、本論文の結果により拓かれていくことが期待される計算量理論の未解決問題についての展望が述べられている。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。