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