权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

递归函数理论在计算复杂性问题中的应用

基本信息

批准号：
05640257
负责人：
篠田壽一
金额：
$ 1.22万
依托单位：
Nagoya University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-05640257/
关键词：
帰納的関数論計算量多項式時間計算可能性決定問題上半束

项目摘要

本研究により、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普遍量との関係を明らかにした(横井)など,研究分担の各分野で本研究に関連して幾つかの新たな結果を得た.

In this study, G.L.Miller defined the possible relationship between the polynomial time and the possible degree of the polynomial time, and studied the possible degree of the polynomial time. The following results are obtained from the number of times of the first round of the round: p-s times of the first round of the round, p-s times of the second round of the round. 1. Calculate the maximum number of possible sets of p-s. 2.0. The number of arbitrary p-s is equal to the minimum upper bound of the minimum pair. 3.The number of possible p-s is equal to the weak Exact Pair Theorem. 4. The EXact Pair Theorem of strong shape is established. 5. Any finite bundle can be used to calculate the upper half of the bundle R^p_s of the p-s times of the possible number of relations. 6. R^p_s of II_2-theory is impossible to determine. R^p_s of first-order theory is impossible to determine. Exact Pair Theorem is a new research topic in the future. In this paper, we introduce the new universal quantity into the solution of the problem of the second order and the basic number, and study the new results of the study.