论文标题
FPRA通过MCMC融合（很少的努力）
FPRAS via MCMC where it mixes torpidly (and very little effort)
论文作者
论文摘要
当知道快速混合可证明失败时，是否可能通过MCMC算法进行完全多项式的随机近似方案（FPRA）？我们分别在平面和二分图上为八个vertex模型介绍了几个维权图。有些是一对一的，而另一些是全息图，以指数式的许多状态从一种环境中绘制出一种类似于量子的多到多种方式的叠加。实际上，我们引入了一组此类映射，这些映射在每种情况下构成了一个组。使用一些全息图及其组成，我们在参数设置处获得了八个vertex模型的FPRA，众所周知，由于固有的屏障，快速混合可证明会失败。该FPRA确实是相同的MCMC算法，除了其状态空间对应于给定状态的叠加，在该状态下，快速混合。还为参数设置提供了FPRA，其中已知自然马尔可夫链会混合曲折的参数设置。我们的结果表明，八个vertex模型是可证明的属性的第一个问题，尽管NP在一般图上近似于近似值（即使是精确复杂性的平面图的＃p-hard），但它在其参数空间的实质区域中都具有fpras。
Is Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for a problem via an MCMC algorithm possible when it is known that rapid mixing provably fails? We introduce several weight-preserving maps for the eight-vertex model on planar and on bipartite graphs, respectively. Some are one-to-one, while others are holographic which map superpositions of exponentially many states from one setting to another, in a quantum-like many-to-many fashion. In fact we introduce a set of such mappings that forms a group in each case. Using some holographic maps and their compositions we obtain FPRAS for the eight-vertex model at parameter settings where it is known that rapid mixing provably fails due to an intrinsic barrier. This FPRAS is indeed the same MCMC algorithm, except its state space corresponds to superpositions of the given states, where rapid mixing holds. FPRAS is also given for torus graphs for parameter settings where natural Markov chains are known to mix torpidly. Our results show that the eight-vertex model is the first problem with the provable property that while NP-hard to approximate on general graphs (even #P-hard for planar graphs in exact complexity), it possesses FPRAS on both bipartite graphs and planar graphs in substantial regions of its parameter space.
