论文标题
随机$ k $ - 满足性公式的最大灵活解决方案
Maximally flexible solutions of a random $K$-satisfiability formula
论文作者
论文摘要
随机$ k $ -sationalizusion（$ k $ -sat）是一种范式模型系统，用于研究约束满意度问题和开发经验算法的相变。随机$ K $ -SAT解决方案空间的统计属性已经进行了广泛的研究，但大多数早期的努力都集中在典型的解决方案上。在这里，我们考虑最大灵活的解决方案，这些解决方案仅使用最小变量数量满足所有约束。这种非典型解决方案具有很高的内部熵，因为它们包含最大数量的空变量，这些变量完全免费选择其状态。每个最大柔性溶液都表示溶液空间的致密区域。我们通过复制对称腔法估算了无效变量的最大分数，并实现了消息通话算法以构建用于单个$ k $ -sat实例的最大灵活解决方案。
Random $K$-satisfiability ($K$-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random $K$-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single $K$-SAT instances.
