免疫集合と単純集合の計算複雑さ

免疫组装和简单组装的计算复杂度

• 批准号: 14740082
• 负责人: 鈴木 登志雄
• 金额: $ 0.96万
• 依托单位: Osaka Prefecture University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14740082/
• 关键词: 免疫集合; 単純集合; 計算量理論; NP; 多項式時間階層; ジェネリック・オラクル; ランダム・オラクル; 命題論理; 計算複雑さ

本研究において,免疫集合と単純集合についてこれまでに得られた一連の結果をまとめ,フランスでの国際研究集会The 3rd IFIP International Conference on Theoretical Computer Science (TCS2004), August 23-26,2004で発表[2]を行なった(発表講演は共著者のYamakami氏による).その内容は論文[1]として出版された.論文[1]に詳細な証明を付けた完全版を論文[3]として投稿した.また,論文[2]の最終校正を行なった.[1]Toshio Suzuki, Tomoyuki Yamakami,"Resource bounded immunity and simplicity (extended abstract),"In : J.Levy et al.eds., Exploring New Frontiers of Theoretical Informatics, pp.81-95,Kluwer Academic Publishers,2004.ISBN 1-4020-8140-5.[2]Toshio Suzuki,"Bounded truth table does not reduce the one-query tautologies to a random oracle,"Archive for Mathematical Logic,掲載決定.[3]Tomoyuki Yamakami, Toshio Suzuki,"Resource bounded immunity and simplicity,"Theoretical Computer Science,投稿中.

The 3rd IFIP International Conference on Theoretical Computer Science (TCS2004), August 23- 26, 2004, was held in Beijing. The content of the paper [1] was published. Paper [1] Detailed proof of full version of paper [3] The final correction of the paper [2] was carried out. [1]Toshio Suzuki, Tomoyuki Yamakami,"Resource bounded immunity and simplicity (extended abstract),"In : J.Levy et al.eds., Exploring New Frontiers of Theoretical Informatics, pp.81-95,Kluwer Academic Publishers,2004.ISBN 1-4020-8140-5. 2. Toshio Suzuki,"Bounded truth table does not reduce the one-query tautomologies to a random oracle,"Archive for Mathematical Logic, Reveal Decisions. 3. Tomoyuki Yamakami, Toshio Suzuki,"Resource bounded immunity and simplicity,"Theoretical Computer Science, in progress.

项目成果

Bounded truth table does not reduce the one-query tautologies to a random oracle

有界真值表不会将单查询重言式简化为随机预言

• 发表时间: 2005
• 期刊: Archive for Mathematical Logic (掲載予定)
• 作者: Toshio Suzuki

Toshio Suzuki: "Degrees of Dowd-type generic oracles"Information and computation. 176・1. 66-87 (2002)

铃木敏夫：《多德型通用预言的度数》信息与计算 176・1（2002）。

Resource bounded immunity and simplicity (extended abstract)

资源有限免疫性和简单性（扩展摘要）

• 发表时间: 2004
• 期刊: Exploring New Frontiers of Theoretical Informatics (単行本)
• 作者: T.Suzuki;T.Yamakami
• 通讯作者: T.Yamakami

Toshio Suzuki: "Complexity of the r-query tautologies in the presence of a generic oracle"Notre Dame journal of formal logic. 41・2. 142-151 (2002)

Toshio Suzuki：“通用预言机中 r 查询同义反复的复杂性”Notre Dame 形式逻辑杂志 41・2（2002 年）。

Toshio Suzuki: "Forcing complexity : minimum sizes of forcing conditions"Notre Dame Journal of Formal Logic. 42. 117-120 (2003)

Toshio Suzuki：“强制复杂性：强制条件的最小尺寸”Notre Dame Journal of Formal Logic。