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

阐明计算中时间和空间能力的差异

• 批准号: 07J02786
• 负责人: 上野 賢哉
• 金额: $ 1.79万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07J02786/
• 关键词: 計算量理論; 論理式; 線形計画法; 通信計算量

本研究計画では、論理式サイズ下界証明技術の改良に関する研究を中心に、計算量クラスの分離という計算量理論の最重要課題へ向けての技術開発を行った。論理式サイズに対して超多項式下界を証明することで、並列化困難性理論との関連から重要な位置づけを占める計算量クラスである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の拡張版を導入した。この手法においては、おおもとの整数計画問題を介さずに全く新しい線形計画定式化法を与えることに成功しており、実際に整数計画問題の最小解をも上回る下界値を与えることが可能であることを証明した。これは、提案技術の極めて高い潜在能力を示唆するものであると同時に、線形計画法及び多面体理論の分野においても意外性の高い結果となっている。

This research project is aimed at improving the lower bound proof technology of logical expressions, and developing the most important problem of computational quantity theory in the research center. The logical expression is related to the lower bound of the superpolynomial. The theory of parallelism is related to the important position. The calculation quantity is separated. The important conclusion is obtained. The computer science is generally related to the important meaning of the essential problem. One side, many years, many researchers, many problems, many solutions, many problems. This study was initiated by Karchmer, Kushilevitz and Nisan in 1995. The lower bound proof technique of logical formula was developed to break through the lower bound of logical formula and to improve the potential of logical formula. Karchmer, Kushilevitz and Nisan, linear planning theory, linear relaxation, two-pair theorem, use of lower bound, logical expression, LP Bound, call method, The method of proof is: the lower bound of the logical expression; the minimum solution of the specific integer program problem; the lower bound of the LP relaxation problem; In recent years, there have been many existing proof methods for LP Bound, including the following: The best lower bound of this proof is Hastad. The LP Bound is a pure proof method. The LP Bound is a proof method. 1. Sherali-Adams Lift-and-Project Method Lift-and-Project Method is a method of proving the existence of a system. The lower bound of the minimum solution of the integer program problem is proved to be possible. 2. The method of the object, the complexity of the form, the abstract concept, the use of the quasi-additive scale, the name of the new form, the LP Bound version, is introduced The method of solving the integer problem is completely new and successful. The high potential of the proposed technique is shown by the high potential of simultaneous, linear, and polyhedral theory.

项目成果

Improved Formula Size Lower Bounds for Monotone Self-Dual Boolean Functions

改进单调自对偶布尔函数的公式大小下界

• 发表时间: 2008
• 作者: 服部 達哉;村上 健太;石田 圭輔;常田 貴夫;斎藤 拓巳;田中 知;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno
• 通讯作者: Kenya Ueno

Breaking the Rectangle Bound Barrier against Formula Size Lower Bounds

打破配方尺寸下限的矩形界限障碍

• 发表时间: 2010
• 期刊: Lecture Notes in Computer Science
• 作者: K.Seto;S.Tamaki;山本修一郎;Kenya Ueno;David Avis;K. Seto and S. Tamaki.;山本修一郎;D. Avis;Kenya Ueno
• 通讯作者: Kenya Ueno

Reversal versus Access:Complexity Classes and Random Combinatorial Strctures

逆转与访问：复杂性类别和随机组合结构

• 发表时间: 2008
• 作者: 服部 達哉;村上 健太;石田 圭輔;常田 貴夫;斎藤 拓巳;田中 知;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno;Kenya Ueno
• 通讯作者: Kenya Ueno

A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

通过团约束对公式大小下界进行更强的 LP 约束

• DOI: 10.1016/j.tcs.2012.02.005
• 发表时间: 2012
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Y. Aoshima;D. Avis;T. Deering;Y. Matsumoto and S. Moriyama;David Avis;Kenya Ueno
• 通讯作者: Kenya Ueno

Relating L versus P to Reversal versus Access and Their Combinatorial Structures

• DOI: 10.1093/ietisy/e91-d.12.2776
• 发表时间: 2008-12
• 期刊: IEICE Trans. Inf. Syst.
• 作者: Kenya Ueno