BriefGPT.xyz
Feb, 2024
利用SAT求解器自动寻找难度缩减
Finding hardness reductions automatically using SAT solvers
HTML
PDF
Helena Bergold, Manfred Scheucher, Felix Schröder
TL;DR
通过基于SAT的框架，我们对具有禁止子结构的符号映射的完整问题进行了首次的彻底研究，并对数千种NP完全问题的结构进行了分类，包括内部三元组系统和推广到更高维度的结构。
Abstract
In this article, we show that the
completion problem
, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many
combinatorial structures
. While the
→