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

超変数を扱える形式的体系の理論的研究

能够处理超变量的形式系统的理论研究

基本信息

批准号：
04F04801
负责人：
佐藤雅彦
金额：
$ 1.54万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-04F04801/
关键词：
計算量理論 NP完全性 #P完全性完全性問題 universal relation sorted logic hybrid logic

项目摘要

本研究では昨年に引き続き,様々な特徴付けによる計算量クラス間の関係に関する研究を行なった.とくに,回路にて特徴付けられる弱い計算量クラス,および,多項式と係数関数によって特徴付けられる計算量クラス間の関係に関する研究を行ない,その結果,以下のような成果が得られた.1.制限された回路による計算量クラスの特徴付けに関する研究本研究では,制限された回路とそれによって特徴付けられる計算量クラスに関する研究を行なった.この研究の成果は,Natacha Portierとの共著論文としてMFCS2006において発表し,論文誌Journal of Complexityへの掲載が決定している.2.Valiantの理論における計算量クラスの完全性問題に関する研究本研究では,Valiantの理論によって定義される計算量クラス階層と,それとは異なる形の限定されたテンソル計算によって定義される計算量クラス階層との間の同等性を見出した.この研究の成果はLogicum Lugdunensis(2006年6月)において招待講演として発表し,近々論文誌への投稿を予定している.3.多項式とその係数関数によって特徴付けられる計算量クラスに関する研究本研究では研究分担者であるMalodの学位論文の結果を拡張し,多項式とその係数関数によって特徴づけられる計算量クラス間の関係に関する研究を行なった.この研究の成果は近々論文誌への投稿を予定している.

This study is aimed at studying the relationship between the characteristics and the computational variables. The study on the relationship between the calculated quantities and the characteristic coefficients of the polynomial is carried out. The results are as follows: 1. The study on the characteristic coefficients of the polynomial is carried out. The research on the control loop and the calculation of the characteristics of the loop. The results of this research were revealed in Natacha Portier's co-authored paper at MFCS2006, and the publication of the paper in the Journal of Complexity determined it. 2. Valiant's theory is related to the completeness of computational complexity. This research focuses on the hierarchy of computational complexity defined in Valiant's theory. The difference between the two types of calculation is shown by the equivalence between the two types of calculation. The results of this research are presented in Logicum Lugdunensis(June, 2006), and the contributions of recent papers are scheduled. 3. Polynomials and coefficient relations are studied. The results of Malod's dissertation are presented. Polynomial coefficient relations are studied in detail. The results of this research are expected to be published in the journal.