帰納的関数論の計算量問題への応用

本研究により、G.L.Millerによって定義された計算可能関数に対する多項式時間計算可能性次数の構造が、p-m次数やp-T次数のような既に研究されてきた多項式時間計算可能性次数の構造と著しい相違をもっていることが明らかになった。すなわち,我々はこの次数をp-s次数と名付け、p-s次数に関して以下の結果を得た。1.計算可能集合のp-s次数は極大元をもち、したがって上半束をなさない。2.0でない任意のp-s次数はminimal pairの最小上界として表される.3.計算可能関数のp-s次数に対して弱い形のExact Pair Theoremが成り立つ。4.強い形のEXact Pair Theoremは成り立たない.5.任意の有限束が計算可能関数のp-s次数のなす上半束R^p_sに埋め込み可能である。6.R^p_sのII_2-理論は決定可能である.R^p_sの一階の理論は決定不可能であると予想されるが本研究中においては証明することができなかった.これは強い形のExact Pair Theoremが成り立たないことからくる困難さによるもので今後の研究課題としたい.この他,実2次体における種数1問題や基本単数に関するArtin予想の解決に向けて新しいD普遍量を導入し,既知のD普遍量との関係を明らかにした(横井)など,研究分担の各分野で本研究に関連して幾つかの新たな結果を得た.

本研究により、G.L.Millerによって定義された計算可能関数に対する多項式時間計算可能性次数の構造が、p-m次数やp-T次数のような既に研究されてきた多項式時間計算可能性次数の構造と著しい相違をもっていることが明らかになった。すなわち,我々はこの次数をp-s次数と名付け、p-s次数に関して以下の結果を得た。1.計算可能集合のp-s次数は極大元をもち、したがって上半束をなさない。2.0でない任意のp-s次数はminimal pairの最小上界として表される.3.計算可能関数のp-s次数に対して弱い形のExact Pair Theoremが成り立つ。4.強い形のEXact Pair Theoremは成り立たない.5.任意の有限束が計算可能関数のp-s次数のなす上半束R^p_sに埋め込み可能である。6.R^p_sのII_2-理論は決定可能である.R^p_sの一階の理論は決定不可能であると予想されるが本研究中においては証明することができなかった.これは強い形のExact Pair Theoremが成り立たないことからくる困難さによるもので今後の研究課題としたい.この他,実2次体における種数1問題や基本単数に関するArtin予想の解決に向けて新しいD普遍量を導入し,既知のD普遍量との関係を明らかにした(横井)など,研究分担の各分野で本研究に関連して幾つかの新たな結果を得た.