回路計算量の下限の研究とその応用

电路复杂度下限及其应用研究

• 批准号: 16092225
• 负责人: 築地 立家
• 金额: $ 8.13万
• 依托单位: Tokyo Denki University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092225/
• 关键词: 計算量理論; NP困難; 近似アルゴリズム; 量子アルゴリズム; 格子ベクトル問題; 有限オートマトン; MOD回路; 計算量の下界問題; 暗号; algorithm; complexity; randomness; graph; circuit; quantum; phylogeny; approximation

1.唯一最短格子ベクトル問題を効率的に解く量子アルゴリズムの設計(築地).(1)唯一最短格子ベクトル問題を,各次元が多項式サイズの環で形成されるような多次元整数環上のサイモン問題に帰着させた.(2)このように一般化されたサイモン問題を,線形計画法の問題に帰着させて,既知のアルゴリズムにより,多項式時間でとけることを確認した.その際、一定の周期dを隠しているような量子状態の観測値と、一様ランダムなる観測値との間に、ある種の期待値に関する一定の差が存在することを確認した。(3)この結果を応用して、2面体群の隠れ部分群問題が量子多項式時間以内に解けることを証明した。2.相関データグラフがエラーを含むときに遺伝系統図を構築する問題がNP完全であることの証明(築地・陳).(1)相関データグラフがエラーを含むときに、遺伝系統図の次数が有限であれば,創刊データグラフからエラーが最小の遺伝系統図を再構築する問題はNP完全であることを証明した。3.有限オートマトンの等価変換と状態数解析(松浦)(1)入力記号が{0,1}で,かつnが奇数である場合に,α≦3n-3の範囲でn状態NFAで,それと等価なDFAが2^n-α状態有するものが存在することを示した。4.六角盤面上の一般三並べの先手必勝問題(松浦)(1)六角盤面上の一般三並べ問題において、4つまでのタイルから成る全ての図形に関して,全てのサイズの盤面に対して,負け型である場合,および,勝ち型である場合は手順の最小性を示した.

1. The only shortest lattice problem is the efficient solution of quantum design (Tsukiji). (1)The only shortest lattice problem is to form a ring of polynomials with multiple integers. (2)This is a generalization of the problem of linear programming, which is known as polynomial time. When a quantum state is measured, a certain period d is determined. When a quantum state is measured, a certain difference is determined. (3)This result is applied to prove that the partial group problem of dihedral groups can be solved in quantum polynomial time. 2. Correlated data sets include data sets, and data sets. (1)The number of times a transmission system is constructed is limited, and the problem of reconstructing a transmission system is NP complete. 3. Analysis of the number of states with finite number of equal changes (Matsuura)(1) In the case where the force symbol is {0,1}, the range of n is odd,α ≤ 3n-3 and the range of n is NFA, the state of n is equal to 2 n-α. 4.(1) The general trilateral problem on hexagonal disk (Matsuura)(2) The general trilateral problem on hexagonal disk (Matsuura)(3) The general trilateral problem on hexagonal disk (Matsuura)(4)(Matsuura)(

项目成果

Recognizing Hole-Free 4-Map Graphs in Cubic Time

识别立方时间内的无孔 4 映射图

• 发表时间: 2006
• 期刊: Algorithmica 45(2)
• 作者: Zhi-Zhong Chen;Michelangelo Grigni;Christos H. Papadimitriou
• 通讯作者: Christos H. Papadimitriou

An Improved Randomized Approximation Algorithm for Max TSP

一种改进的最大TSP随机逼近算法

• 发表时间: 2005
• 期刊: Journal of Combinatorial Optimization 9
• 作者: Zhi-Zhong;Chen;T.;Nagoya;Zhi-Zhong Chen;Lusheng Wang;Zhi-Zhong Chen;Zhi-Zhong Chen;Tatsuie Tsukiji;Zhi-Zhong Chen;Zhi-Zhong Chen
• 通讯作者: Zhi-Zhong Chen

Improved approximation algorithms for metric MaxTSP

• DOI: 10.1007/s10878-006-9023-7
• 发表时间: 2005-10
• 期刊: Journal of Combinatorial Optimization
• 影响因子: 1
• 作者: Zhi-Zhong Chen;Takayuki Nagoya

Computing Phylogenetic Roots with Bounded Degrees and Errors Is Hard

计算具有有限度和误差的系统发育根很困难

• 发表时间: 2006
• 期刊: Theoretical Computer Science 363(1)
• 作者: Tatsuie Tsukiji;Zhi-Zhong Chen
• 通讯作者: Zhi-Zhong Chen

Limit laws for terminal nodes in random circuits with restricted fan-out; a family of graphs generalizing binary search trees

扇出受限的随机电路中终端节点的限制法则；

• 发表时间: 2004
• 期刊: Acta Informatica vol.40
• 作者: Tatsuie Tsukiji;Hosam Mohmoud
• 通讯作者: Hosam Mohmoud