回路計算量理論に基づいた脳の計算原理の解明

基于电路复杂性理论阐明大脑计算原理

• 批准号: 12J03660
• 负责人: 鈴木 顕
• 金额: $ 1.15万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012 至 2014-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12J03660/
• 关键词: エネルギー複雑度; 計算時間; しきい値回路; 素子数; 対称関数; ファンイン

昨年度の報告書で述べたとおり, 本年度は当初の予定を変更し, 「1. 計算時間を考慮したしきい値回路の設計および解析」に従事した. 昨年度従事した, 「2. より複雑な情報処理タスクの実現」に関する結果を利用することで, より厳密な計算時間の解析を行うことができた. 具体的には, 脳の情報処理の仕組みとして比較的研究の進んでいる画像認識に関わる関数を計算するしきい値回路に対して, 計算時間を制限した際にその計算能力にどのような影響があるかについて研究を行った. その結果, 計算時間を制限すると, 素子数やファンインが大きくならざるを得ないことを示すことに成功した. また, どの程度大きくする必要があるかについて解析を進めた結果, 最低限必要な素子数やファンインの値を正確に与えることに成功した. 研究結果の一部はすでに国際会議や学術雑誌に投稿済みであり, そのうちいくつかはすでに受理, 発表, 発行が済んでいる. 残る成果についても, 随時論文を執筆し, まとまり次第国際会議や学術雑誌に投稿する予定である.また, 本年度は昨年度得られた複数の結果についても, それぞれ国際会議「Asian Association forAlgorithms and Computation」及び「Theory and Applications of Models of Computation」等で発表を行った. さらに, 昨年度学術雑誌へ投稿していた論文は「Theoretical Computer Science (TCS)」受理され, 発行になった.

Yesterday's annual report was revised, and this year's report was revised,"1. The calculation time is taken into account in the design and analysis of the loop. Last year's event,"2. The result of complex information processing is utilized, and the calculation time is analyzed. Specifically, the information processing system and the comparative study of the progress of image recognition, related to the calculation of the value of the loop, the calculation time limit, the calculation capacity of the impact of the study. As a result, the calculation time is limited, and the number of elements and information can be obtained as quickly as possible. This is a success. The minimum number of elements necessary for analysis is correct and the minimum number of elements necessary for analysis is successful. Some of the research results are submitted to international conferences and academic journals, accepted, presented and implemented. The results of the study are published at any time, and the contributions to the second international conference and academic journals are scheduled. This year, the results of the Asian Association for Algorithms and Computation and the Theory and Applications of Models of Computation were presented. Today, last year's Academic Journal submission was accepted and published in Theoretical Computer Science (TCS).

项目成果

Energy effcient threshold circuits detecting global pattern in 1-dimensional arrays

检测一维阵列中全局模式的节能阈值电路

• 发表时间: 2013
• 作者: Akira Suzuki;Kei Uchizawa and Xiao Zhou
• 通讯作者: Kei Uchizawa and Xiao Zhou

On the Minimum Caterpillar Problem in Digraphs

有向图中的最小毛毛虫问题

• DOI: 10.1587/transfun.e97.a.848
• 发表时间: 2014
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Taku Okada;Akira Suzuki;Takehiro Ito and Xiao Zhou
• 通讯作者: Takehiro Ito and Xiao Zhou

Packing Trominoes is NP-Complete, #P-Complete and ASP-Complete

包装 Trominoes 是 NP 完全的，

• 发表时间: 2012
• 作者: Takashi Horiyama;Takehiro Ito;Keita Nakatsuka;Akira Suzuki and Ryuhei Uehara
• 通讯作者: Akira Suzuki and Ryuhei Uehara

Hitori Number

人数

• 发表时间: 2012
• 作者: Takashi Horiyama;Takehiro Ito;Keita Nakatsuka;Akira Suzuki and Ryuhei Uehara;Akira Suzuki. Kei Uchizawa and Xiao Zhou
• 通讯作者: Akira Suzuki. Kei Uchizawa and Xiao Zhou

On the Parameterized Complexity for Token Jumping on Graphs

• DOI: 10.1007/978-3-319-06089-7_24
• 发表时间: 2014-04
• 作者: Takehiro Ito;M. Kaminski;H. Ono;Akira Suzuki;Ryuhei Uehara;Katsuhisa Yamanaka