安本雅洋（数理論理学）

Peanoの公理の超準モデルの構造の研究とその応用

　超準モデルの応用は，１９６０年代にA.Robinsonによる解析学への応用が最初で無限小の概念の合理的な使用によって解析学の基礎付けが可能であることを示した．その後１９７０年代にはA.RobinsonとP.Roquetteは整数環及び有理数体の超準モデルとそれらの有限次代数拡大体に埋め込まれる関数体の構造との関係，特に両者のdivisorが比例するとともにある種のdivisorの次数の限界がRothの不等式をを使って表されることを示し，その結果を不定方程式論をはじめとする整数論，特に代数曲線上の整数点に関するSiegelの定理の証明やHilbertの既約性定理の研究などに使った． iteratedな超準モデルの使用などこれらの方法をさらに発展させることにより，ヒルベルトの既約性定理が成立する範囲の限界の決定等において従来の代数的手法では得られない結果が得られる．特に代数体と代数関数体の類似性が超準モデルの手法を使って表現することによって，よりいっそう明確になり，それらの応用可能性は代数曲面の整数点の分布の研究にもつながっている．

　超準解析においては飽和モデルをはじめとして非常に強い超準モデルが使用されているのに対して，１９８０年代半ばから弱い算術，特に限定算術の超準モデルの研究がさかんになりつつある．限定算術はＳ.Ｂussによって始められたもので，多項式時間計算量の理論の数学的基礎理論として重要なものである．この弱い算術の超準モデルにより，大きい数(２進表示された数)と小さい数(桁数として使用される数，i.e.２進表示された数のbitの長さ)の区別が明確になる．通常の自然数で考えている限りこの両者は概念としては区別されても，数としては区別されないものであったが，超準モデルの使用により両者は区別可能となり，小さい数を保存したまま大きい数を拡大するといった方法が開発されるようになった．このことを使い最初に意味のある結果を得たのはＡjtaiで，弱い算術の超準モデル上にforcing methodを応用することによってPHP(Pigeon hole principle)が多項式sizeで深さ有限のBoolean formulaでは書けないことを示した．この方法を限定算術の超準モデルのBool値拡大の理論に一般化することにより，弱い算術においては数え上げ(Counting)がPHPより強い条件であることが証明できる．またBool代数を多項式sizeのBoolean circuitを含むように拡大することによって，多項式時間計算量の階層の分離問題，特に計算量理論の中で最も重要な未解決問題と言われているＰ＝ＮＰ問題との関係に関する研究に役立てることが可能になった．さらにオラクル部分のBool拡大への発展が考えられるが今のところ有効な理論はできていない．このようにして計算量理論の問題が超準モデルのBool代数のイデアルの完全性の構造の問題として取り扱えることがわかり，新しい視点からＰ＝ＮＰ問題に取り組むことができる．Bool値拡大の方法は公理的集合論において数多くの優れた結果を生み出しており，同様のことが計算量の理論においても期待できる．

前のページに戻る

Last modified: Fri Nov 22 14:28:51 1996