Guided Search and a Faster Deterministic Algorithm for 3-SAT
Guided Search and a Faster Deterministic Algorithm for 3-SAT
复制标题
3-SAT 的引导搜索和更快的确定性算法
DOI：
10.1007/978-3-540-78773-0_6
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Dominik Scheder
中科院分区：
文献类型：
--
作者：
Dominik Scheder
NP难问题的大多数确定性算法是分裂算法：它们将问题实例分裂成几个较小的问题，然后递归求解。通常，算法可以在几种分裂之间进行选择。对于3-SAT，我们表明，明智地选择哪种分裂应用，可以避免遇到太多的最坏情况的情况。这将3-SAT当前最著名的确定性最坏情况运行时间从提高到，n是输入公式中的变量数。
Most deterministic algorithms for NP-hard problems aresplitting algorithms: They split a problem instance into several smaller ones, which they solve recursively. Often, the algorithm has a choice between several splittings. For 3-SAT, we show that choosing wisely which splitting to apply, one can avoid encountering too many worst-case instances. This improves the currently best known deterministic worst case running time for 3-SAT fromto,nbeing the number of variables in the input formula.