期刊专题

10.3969/j.issn.1002-137X.2013.02.056

Ising图模型概率推理的计算复杂性

引用
图模型概率推理的主要任务是通过对联合概率分布进行变量求和来计算配分函数、变量边缘概率分布、条件概率分布等.图模型概率推理计算复杂性及近似概率推理的计算复杂性是一重要的理论问题,也是设计概率推理算法和近似概率推理算法的理论基础.研究了Ising图模型概率推理的计算复杂性,包括概率推理的难解性及不可近似性.具体地,通过构建#2 SAT问题到Ising图模型概率推理问题的多项式时间计数归约,证明在一般Ising图模型上计算配分函数、变量边缘概率分布、条件概率分布的概率推理问题是#P难的,同时证明Ising图模型近似概率推理问题是NP难的,即一般Ising图模型上的概率推理问题是难解且不可近似的.

Ising图模型、概率推理、计算复杂性、难解性、不可近似性

40

TP181(自动化基础理论)

天津市高等学校科技发展基金计划项目20110806;天津科技大学引进人才基金20110404

2013-03-21(万方平台首次上网日期,不代表论文的发表时间)

共5页

253-256,288

暂无封面信息
查看本期封面目录

计算机科学

1002-137X

50-1075/TP

40

2013,40(2)

专业内容知识聚合服务平台

国家重点研发计划“现代服务业共性关键技术研发及应用示范”重点专项“4.8专业内容知识聚合服务技术研发与创新服务示范”

国家重点研发计划资助 课题编号:2019YFB1406304
National Key R&D Program of China Grant No. 2019YFB1406304

©天津万方数据有限公司 津ICP备20003920号-1

信息网络传播视听节目许可证 许可证号:0108284

网络出版服务许可证:(总)网出证(京)字096号

违法和不良信息举报电话:4000115888    举报邮箱:problem@wanfangdata.com.cn

举报专区:https://www.12377.cn/

客服邮箱:op@wanfangdata.com.cn