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

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

基本信息

批准号：
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の学位論文の結果を拡張し,多項式とその係数関数によって特徴づけられる計算量クラス間の関係に関する研究を行なった.この研究の成果は近々論文誌への投稿を予定している.

延续去年，在本研究中，我们对具有各种特征的复杂性类别之间的关系进行了研究。特别是，我们重点研究了以电路为特征的弱复杂性类别，以及以多项式和系数函数为特征的复杂性类别。，我们对计算复杂性类别之间的关系进行了研究。这项研究的结果由 Natacha 发表与Portier合着的论文发表在MFCS2006上，并已决定发表在Journal of Complexity杂志上。2．Valiant理论中复杂性类的完整性问题的研究我们发现了复杂性类层次结构之间的等价性。由不同形式的受限张量计算定义。我在 Lugdunensis 上做了一次受邀演讲（2006 年 6 月），并计划很快将其提交给期刊。 3. 以多项式及其系数函数为特征的复杂性类的研究扩展 Malod 论文的成果，我们对复杂性之间的关系进行了研究。以多项式及其系数函数为特征的类。这项研究的结果计划很快提交给期刊。