该研究提出了一种基于单词级哈希函数的模型计数方法,可以直接利用复杂的 SMT 求解器,为概率推理中的计数问题提供了新思路。
Nov, 2015
本文研究了命题模型计数问题,针对约束条件表达式分别为 DNF 公式和 CNF 公式分别介绍了 Monte Carlo 和基于哈希的计数技术,并提出了两种新算法技术:Symbolic Hashing 和 Stochastic Cell Counting,通过设计基于哈希的 FPRAS for DNF counting 提高了效率和应用价值。
Oct, 2017
本文探讨了一种利用通用哈希和 SAT 求解器的方法,可以在不牺牲正确性保证的同时,处理具有数十万个变量的公式,解决了人工智能中受限采样和计数的两个基本问题,这对于概率推理及规划,约束随机验证等方面有着广泛应用,并探讨一些需要解决的挑战。
Dec, 2015
介绍了一种基于 SAT 求解器的算法和实现工具,用于处理大规模的 CNF 公式的近似计数问题。通过多项式调用的方式,能够高精度地估算满足条件的解数,同时针对过大的问题仍能提供高置信度的估算边界。
Jun, 2013
该研究论文探讨了如何通过增加短的随机奇偶约束来计算公式满足的真实赋值(模型),实现 NP 问题的计数,尤其是当需要添加多个约束时,随机奇偶约束的集合解的几何结构类似于纠错编码,得到了严格的数学保证。
Jul, 2017
研究了哈希算法在计算 Boolean 公式中的模型数量时,delta 值较小会对可伸缩性造成重大影响。提出了一种基于 Rounding 的新方法和一种新算法(RoundMC),用于高置信度下的估计,可以显著提高运行时性能。RoundMC 能够比当前技术水平更好地解决问题,速度提高了 4 倍。
May, 2023
本文介绍了一种新的方法,使用黑箱预言机,通过 NP-Oracle 实际求解带权重赋值的模型计数问题和分布感知的满足分配的抽样问题,从而在中等规模的问题上获得了强大的理论保证。
Apr, 2014
提出使用有限独立哈希的新方法来解决 boolean satisfiability 问题,并基于此方法设计了两个实用算法:一个近似均匀生成器和一个可扩展的近似模型计数器,该方法具有强大的理论保证和可扩展性,可适用于不同的应用领域。
我们提出了第一个近似模型计数的认证框架,并且证明了其输出近似值的质量保证。
Jun, 2024
模型计数、近似计数算法、可审核的近似计数器、证书和 oracle
Dec, 2023