How to select constraints that help algorithms approximately solve constraint satisfaction problems

如何选择有助于算法近似解决约束满足问题的约束

• 批准号: 24500011
• 负责人: YAMAKAMI TOMOYUKI
• 金额: $ 3.41万
• 依托单位: University of Fukui
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012-04-01 至 2015-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-24500011/
• 关键词: 制約充足問題; 最適化問題; 数え上げ問題; アルゴリズムの効率; ＃P完全; 対数領域計算; プッシュダウンオートマトン; ２極値定理; リスト行列グラフ分割問題; 時間計算量; プッシュダウン・オートマトン; 制約充足問題の最適解探索; 解の数え上げ問題; 対数領域計算可能性; 固定長領域計算量; リスト分割数え上げ問題; 時間・領域計算量; 解法アルゴリズムの効率; 小型計算機端末; 最適解近似アルゴリズム; 多項式時間; 近似保存還元性; Holant問

项目成果

Quantum and Reversible Verification of Proofs Using Constant Memory Space

• DOI: 10.1007/978-3-319-13749-0_13
• 发表时间: 2014-12
• 作者: Marcos Villagra;T. Yamakami

Approximate counting for complex-weighted Boolean constraint satisfaction problems

复数加权布尔约束满足问题的近似计数

• DOI: 10.1016/j.ic.2012.08.002
• 发表时间: 2012
• 期刊: Information and Computation
• 影响因子: 1
• 作者: T. Horiyama;T. Ito;K. Nakatsuka;A. Suzuki;R. Uehara;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

Computational Indistinguishability Between Quantum States and Its Cryptographic Application

• DOI: 10.1007/s00145-011-9103-4
• 发表时间: 2012-07-01
• 期刊: JOURNAL OF CRYPTOLOGY
• 影响因子: 3
• 作者: Kawachi, Akinori;Koshiba, Takeshi;Yamakami, Tomoyuki
• 通讯作者: Yamakami, Tomoyuki

Tomoyuki Yamakami Homepage

山上智之主页

Counting list matrix partitions of graphs

计算图的列表矩阵分区

• 发表时间: 2015
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: A. Goebel;L. A. Goldberg;C. McQuillan;D. Richerby;and T. Yamakami
• 通讯作者: and T. Yamakami