著者

佐藤 潤也 松本 裕行 松原 洋 吉信 康夫 松本 耕二 谷川 好男

出版者

名古屋大学

雑誌

基盤研究(C)

巻号頁・発行日

2003

---

(1)形式群に付随するBernoulli多項式に対してdistribution relationを与えることが出来た.(2)自然数kを固定したとき,1,2,・・・,kに対するk乗剰余が全て異なるような素イデアルの存在を考えることは,符号理論への応用の観点から重要であることが知られている.本来,この問題は,初等整数論で述べられた有理素数に関する問題であったが,べき剰余記号を用いて言い換えることにより,問題の本質が浮き彫りとなり,有理数体のアーベル拡大における素イデアルの問題に帰着され,本研究において,部分的な解決がなされた.すなわち,k【less than or equal】7に対して,(I)上記の素イデアルは存在する.さらに,(II)正の密度が存在し,クロネッカー式密度を計算することができる.以上から,条件を満たす素イデアルが無限に多く存在することが分かった.証明には,類体論とチェボタレフの密度定理を用いる.また,k=3の場合には,イデアル群として特徴づけられることを示した.k【less than or equal】7と言う条件は,本質的な条件ではなく,kを具体的に一つ与えれば,同様の結果を導くことができる.(3)符号理論における未解決問題の一つ:『法3pの乗法群において,位数p-1をもち,(p-1)/2乗が-1と合同であるが,2を生成しない整数が存在するか?』が,本質的に平方剰余記号の第2補充法則と同値であることを証明し,肯定的に解決した.

著者

松原 洋 小澤 正直 吉信 康夫 築地 立家 佐藤 潤也 井原 俊輔 三井 斌友

出版者

名古屋大学

雑誌

基盤研究(C)

巻号頁・発行日

1999

---

計算可能性と多項式時間計算可能性の分野は、集合論、帰納的関数論、計算量理論、学習理論、確率モデル論、量子計算量理論等と密接に関係しており、本研究の研究実績も多岐にわたる.以下はそれぞれの分野における成果のいくつかを報告する.詰め将棋の計算量:8×8の桝目をn×nに拡張し、コマの個数をo(n)にして詰め将棋を作成したとき、一般化詰め将棋問題はEXPTIME完全であることを示した.これにより、一般化将棋もEXPTIME完全であることになる.確率モデル:一様ランダムに生成される回路の出力端子の個数の分布を決定した.学習1:負例のみからなるサンプルと無矛盾なo(logn)長の単調単項式を提出する問題の計算複雑さは、AND-OR-AND型の3段並列回路でo((logn)^2)個の入力変数をもつものの充足回発見問題と対数領域還元について同等であることをしめした.学習2:包除の原理を応用してDNF式を2^<o(√n)>時間で学習するアルゴリズムをえた.さらに、これ以上高速には学習できないことを頑健学習モデルの上で証明した.学習3:o(logn)個の変数に依存する一般の関数について、その関係変数を高速に発見する3種類のアルゴリズムを提案した.吉信はApproachability Propertyという無限組合せ論の命題と、ある条件を満たしたゲームの必勝法の存在のextendabilityという性質が同値だということを証明した.松原はS.Shelahとの共同研究でλがstrong limit singular cardinalであれば、NS_<kλ>はprecipitousにはなれないことを証明した.さらにこの結果を使って、Menasの予想がλがstrong limit singular cardinalの場合に成立することを証明した.