lisp - 子集求和问题和 NP 完全问题的可解性

Question

当我想出一个似乎是解决它的通用算法时，我正在阅读子集和问题:

(defun subset-contains-sum (set sum)
    (let ((subsets) (new-subset) (new-sum))
        (dolist (element set)
            (dolist (subset-sum subsets)
                (setf new-subset (cons element (car subset-sum)))
                (setf new-sum (+ element (cdr subset-sum)))
                (if (= new-sum sum)
                    (return-from subset-contains-sum new-subset))
                (setf subsets (cons (cons new-subset new-sum) subsets)))
            (setf subsets (cons (cons element element) subsets)))))

“set”是一个不包含重复项的列表，“sum”是要搜索子集的总和。 “subsets”是一个 cons 单元列表，其中“car”是一个子集列表，“cdr”是该子集的总和。只需将元素放在前面，即可在 O(1) 时间内从旧子集创建新子集。

我不确定它的运行时复杂度是多少，但似乎随着每个元素“总和”的增长，“子集”的大小加倍，加一，所以在我看来至少是二次的。

我发布这个是因为我之前的印象是 NP 完全问题往往是棘手的，并且通常可以希望最好的是启发式，但这似乎是一个通用的解决方案，假设你有CPU周期，总能给你正确答案。还有多少 NP 完全问题可以像这个一样解决？

Answer 1

NP 完全问题是可以解决的，只是不能在多项式时间内解决(据我们所知)。也就是说，一个 NP 完全问题可能有一个可以解决它的 O(n*2^n) 算法，但它不会有，例如，一个 O(n^ 3)算法求解。

有趣的是，如果为任何 NP 完全问题找到一个快速(多项式)算法，那么 NP 中的每个问题都可以在多项式时间内解决。这就是 P=NP 的意义所在。

如果我正确理解你的算法(这更多地基于你的评论而不是代码)，那么它等同于 O(n*2^n) 算法 here .有 2^n 个子集，由于您还需要对每个子集求和，因此算法为 O(n*2^n)。

关于复杂性的另一件事 - O(whatever) 仅表示特定算法的扩展程度。您不能比较两种算法并据此说一个比另一个快。 Big-O 符号不关心实现细节和优化 - 可以编写同一算法的两个实现，其中一个比另一个快得多，即使它们可能都是 O(n^2)。一个女人生 child 是一项 O(n) 操作，但很可能这将比大多数 O(n*log(n)) 花费更长的时间排序你执行。基于此，您只能说，对于 n 上的非常大的值，排序会变慢。