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

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

基本信息

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

在这项研究中，在去年之后，我们通过各种特征对计算类别之间的关系进行了研究。特别是，我们对以多项式和系数函数为特征的电路和计算类别之间的关系进行了研究，并获得了结果，结果得到如下：1。研究计算类表征的研究通过限制了本研究的电路，我们对有限电路和计算类别进行了研究。这项研究的结果发表在MFCS2006中，作为与Natacha Portier共同撰写的论文，并已决定发表在《复杂性杂志》上。2。在这项研究中，对英勇理论中计算类别的完整性的研究，我们发现由英勇的理论和计算类别层次结构定义的计算类别层次结构之间的等效性，这些层次结构由不同形式的有限张量计算定义。这项研究的结果是逻辑。他在Lugdunensis（2006年6月）担任邀请演讲，并计划很快提交日记。3。对以多项式为特征的计算复杂类别的研究及其系数功能这一研究扩大了研究人员MALOD的论文的结果，并研究了以多项式为特征的计算复杂类别之间的关系及其系数功能。这项研究的结果计划很快提交给日记。