子集和问题以及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"是搜索子集的总和."子集"是缺点单元的列表,其中"car"是子集列表,"cdr"是该子集的总和.新的子集是在O(1)时间内从旧的子集创建的,只需将元素放在前面即可.

我不确定它的运行时复杂性是什么,但似乎随着每个元素"sum"的增长,"子集"的大小加倍,加上一个,所以在我看来至少是二次的.

我发布这个是因为我以前的印象是NP完全问题往往是难以处理的,并且通常希望最好的问题是启发式,但这似乎是一个通用的解决方案,假设你有CPU周期,总能给你正确的答案.有多少其他NP完全问题可以解决这个问题？

Answer 1

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

有趣的是,如果找到任何NP完全问题的快速(多项式)算法,那么NP中的每个问题都可以在多项式时间内求解.这就是P = NP的意思.

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

关于复杂性的另一件事 - O(whatever)唯一表明特定算法的扩展程度.你不能比较两种算法,并说一种算法比另一种算法更快.Big-O表示法并不关心实现细节和优化 - 可以编写相同算法的两个实现,其中一个比另一个快得多,即使它们可能都是O(n^2).一个女人制作婴儿是一种O(n)手术,但是这可能比O(n*log(n))你表现的大多数种类花费更长的时间.基于此,您可以说,对于n上的非常大的值,排序会更慢.

Answer 2

所有NP完全问题都有解决方案.只要你愿意花时间计算答案,那就是.仅仅因为没有一种有效的算法,并不意味着没有一种算法.例如,您可以迭代每个可能的解决方案,并最终得到一个.这些问题在现实世界的计算中被广泛使用.如果您需要指数时间(或更糟!)来解决问题,您只需要小心自己为自己设置的问题.