论文标题
主要是单调概率令人满意问题的扰动方法
Perturbative methods for mostly monotonic probabilistic satisfiability problems
论文作者
论文摘要
逻辑表达式的概率令人满意是一种基本概念，称为统计物理和现场理论中的分区函数，对数学中相关图的Tutte多项式的评估以及该图在工程学中的Moore-Shannon网络可靠性。这是在不确定性下决策的关键要素。毫不奇怪，事实证明，要精确计算甚至近似。这些应用中的许多仅与解决方案是单调函数的一部分问题有关。在这里，我们将统计物理学的弱和强耦合方法扩展到异质的满足性问题，并引入了一种新颖的方法，以在单调问题的近似误差上构建下限和上限。这些界限结合了来自两个扰动分析的信息，以产生紧密的界限，从某种意义上说，它们与某些问题实例饱和，这些实例与任何近似值中包含的所有信息都兼容。
The probabilistic satisfiability of a logical expression is a fundamental concept known as the partition function in statistical physics and field theory, an evaluation of a related graph's Tutte polynomial in mathematics, and the Moore-Shannon network reliability of that graph in engineering. It is the crucial element for decision-making under uncertainty. Not surprisingly, it is provably hard to compute exactly or even to approximate. Many of these applications are concerned only with a subset of problems for which the solutions are monotonic functions. Here we extend the weak- and strong-coupling methods of statistical physics to heterogeneous satisfiability problems and introduce a novel approach to constructing lower and upper bounds on the approximation error for monotonic problems. These bounds combine information from both perturbative analyses to produce bounds that are tight in the sense that they are saturated by some problem instance that is compatible with all the information contained in either approximation.
