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

摘要：

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

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

所属期刊栏目：40

分类号：TP181(自动化基础理论)

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

在线出版日期：2013-03-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：253-256,288