計算における時間と空間の能力差の解明

点击翻译按钮获取中文摘要

本研究計画では、論理式サイズ下界証明技術の改良に関する研究を中心に、計算量クラスの分離という計算量理論の最重要課題へ向けての技術開発を行った。論理式サイズに対して超多項式下界を証明することで、並列化困難性理論との関連から重要な位置づけを占める計算量クラスであるNC1とそれを含む計算量クラスを分離するといった重大な結論が得られるなど、計算機科学全般に渡って非常に重要な意味を持つ本質的問題である。一方で、長年に渡り多くの研究者がこの問題に取り組んできたが、その解決には程遠い。本研究では、Karchmer, Kushilevitz and Nisanが1995年に発表した論理式サイズ下界証明技法に着目し、その技術が打ち当たってきた下界値証明に対する限界を突破し、その潜在可能性を飛躍的に発展させるような研究を行ってきた。Karchmer, Kushilevitz and Nisanは、線形計画理論における線形緩和・双対定理を利用し、論理式サイズ下界を与えるLP Boundと呼ばれる手法を導入した。彼らの証明手法では、論理式サイズの下界を、ある特定の整数計画問題の最小解として定式化し、そのLP緩和の双対問題に対する実行可能界を与えることで下界値を与える。近年、このLP Boundが多くの既存の証明手法を包括することが明らかにされてきた。これには、最良の下界を示したHastadによる証明の主補題も含まれている。したがって、おおもとのLP Boundを純粋に拡張した証明手法を与えることで、既存の多くの手法を包括する手法を開発したことになり、実際に下界値を改良するための有望な方向性を提案することになる。1つ目の方法では、Sherali-AdamsのLift-and-Project Methodと呼ばれる手法を利用し、LP Boundを強化した。Lift-and-Project Methodは、体系的に既存の証明手法の障壁となる整数性ギャップと呼ばれるものを無くすことができる技法である。これにより、原理的に整数計画問題の最小解に一致する下界値を証明可能な技法を提案したことになり、研究の究極的目的である超多項式下界を証明する可能性のある極めてポテンシャルの高い証明技法が提案できることになる。2つ目の方法においては、形式的複雑性尺度と呼ばれる抽象的概念を利用して、擬加法的尺度と名付けられた全く新しい形式のLP Boundの拡張版を導入した。この手法においては、おおもとの整数計画問題を介さずに全く新しい線形計画定式化法を与えることに成功しており、実際に整数計画問題の最小解をも上回る下界値を与えることが可能であることを証明した。これは、提案技術の極めて高い潜在能力を示唆するものであると同時に、線形計画法及び多面体理論の分野においても意外性の高い結果となっている。