在给定无限数量的处理单元和无限空间的情况下，是否有可能在合理的时间内解决 O(n!) 复杂度的问题？
O(n!) 问题的典型示例是蛮力搜索：尝试所有排列（有序组合）。
问问题
787 次
10 回答
6
确实是。考虑严格的 NP 形式的旅行推销员问题：给定从每个点到另一个点的旅行成本列表，你能把一个成本小于 K 的旅行放在一起吗？使用 Intel 的新无限核 CPU，您只需为每个可能的排列分配一个内核，然后将成本加起来（这很快），然后查看是否有任何内核标记成功。
更一般地说，NP 中的问题是一个决策问题，这样一个潜在的解决方案可以在多项式时间内（即有效地）得到验证，因此（因为潜在的解决方案是可枚举的）任何这样的问题都可以用足够多的 CPU 来有效地解决。
于 2010-03-29T16:52:46.720 回答
6
听起来您真正要问的是在非确定性机器上是否可以将 O(n!) 复杂度的问题简化为 O(n^a) ；换句话说，是否 Not-P = NP。这个问题的答案是否定的，有一些不是 NP 的非 P 问题。例如，有限的停止问题（询问程序是否最多停止 n! 步）。
于 2010-03-29T16:56:37.103 回答
2
问题在于分配工作和收集结果。
如果所有的 CPU 可以一次读取同一块内存，并且每个 CPU 都有一个唯一的 CPU-ID 并且它知道，那么这个 ID 可以用来选择一个排列，并且分布问题可以在常数时间内解决.
但是，收集结果会很棘手。每个 CPU 可以与其（数字）邻居进行比较，然后将该结果与两个最近邻居的结果进行比较，等等。这将是一个 O(log(n!)) 过程。我不确定，但我怀疑 O(log(n!)) 是超多项式，所以我认为这不是一个解决方案。
于 2010-03-29T16:59:20.123 回答
1
如果问题是检查复杂性 O(n!) 问题的排列/答案之一，那么您当然可以使用无限数量的处理器有效地完成它。
原因是您可以轻松地以对数效率分布问题的原子部分（例如，问题的原子部分可能是要检查的排列之一）。
作为一个简单的示例，您可以将处理器设置为“二叉树”，可以这么说。您可以在根部，让处理器将问题的排列（或问题的最小部分）传递给叶处理器来解决，最终您将在 log(n!)时间。
请记住，将排列传递给处理器需要很长时间。问题本身的每个部分实际上都会立即得到解决。
编辑：根据下面的评论修复了我的帖子。
于 2010-03-29T17:01:11.167 回答
1
不，N！甚至高于NP。认为无限并行可以在多项式时间内解决NP问题，这通常被认为是“合理的”时间复杂度，N！在这种设置下，问题仍然高于多项式。
于 2010-03-29T17:28:20.063 回答
1
您提到搜索是一个“典型”问题，但您实际上是否专门询问过搜索问题？如果是这样，那么是的，搜索通常是可并行的，但据我所知，O(n!) 原则上并不意味着可用的并发程度，是吗？你可能有一个完全串行的 O(n!) 问题，这意味着无限的计算机将无济于事。我曾经遇到过一个不寻常的 O(n^4) 问题，实际上是完全连续的。
因此，可用的并发是第一件事，恕我直言，您应该在面试中提出阿姆达尔定律而获得积分。下一个潜在的陷阱是处理器间的通信，以及算法的一般性质。例如，考虑以下应用程序类列表：http: //view.eecs.berkeley.edu/wiki/Dwarf_Mine。FWIW 我之前提到的 O(n^4) 代码属于 FSM 类别。
另一个与此相关的轶事：我听说超级计算机供应商的一位工程师声称，如果他们 10% 的 CPU 时间花在 MPI 库中，他们认为并行化是一个巨大的成功（尽管这可能仅限于计算化学领域）。
于 2010-03-29T17:53:46.243 回答
1
这就像问无数只猴子在带有文字处理器的防猴子破坏计算机上打字是否可以写出莎士比亚的所有作品；给定无限的时间。现实主义者会说不，因为条件在物理上是不可能的。理想主义者会说是；理论上它可以发生。由于软件工程（Software Engineering，而不是计算机科学）专注于我们可以看到和触摸到的真实系统，那么答案是否定的。如果你怀疑我，那就去建造它并证明我错了！恕我直言。
于 2010-03-29T18:03:15.553 回答
1
有时正确的答案是，“你的代码库出现了多少次？” 但在这种情况下，有一个真正的答案。
正确答案是否定的，因为并非所有问题都可以使用完美的并行处理来解决。例如，一个类似旅行推销员的问题必须致力于一条路径，才能考虑旅程的第二段。
假设一个完全连接的城市矩阵，如果你想为我们疲惫的推销员显示所有可能的非循环路线，你会遇到一个 O(n!) 问题，这个问题可以分解为 O(n)*O( (n-1)!) 问题。问题是您需要先承诺一条路径（在等式的 O(n) 一侧），然后才能考虑剩余的路径（在等式的 O((n-1)!) 一侧）。
由于某些计算必须在其他计算之前执行，因此无法在单个散布/收集过程中完美地散布结果。这意味着解决方案将等待必须在“下一步”开始之前出现的计算结果。这是关键，因为对先前部分解决方案的需求为继续计算的能力提供了“瓶颈”。
既然我们已经证明我们可以让这些无限快、无限多的 CPU 等待（即使它们正在等待自己），我们知道运行时间不可能是 O(1)，我们只需要选择一个非常大 N 以保证“不可接受的”运行时间。
于 2010-03-29T19:21:07.313 回答
0
忽略设置成本（例如，可能是什么......将一系列值分配给处理单元），然后是的。在这种情况下，任何小于无穷大的值都可以在相同数量的处理单元的一次并发迭代中求解。
然而，设置是一件很重要的事情，不容忽视。
于 2010-03-29T16:47:16.913 回答
0
每个问题都可以由一个 CPU 解决，但谁会将这些工作交付给所有无限的 CPU？一般来说，这个任务是集中的，所以如果我们有无限的工作要交付给所有无限的 CPU，我们可能需要无限的时间来完成。
于 2010-03-29T17:03:07.073 回答