blocks|key|1022918|text|就是。考虑严格NP形式的旅行推销员问题:给定从每个点到另一个点的旅行费用列表，您能将费用小于K的旅行组合在一起吗？有了英特尔新的无限核心CPU，您只需为每个可能的排列分配一个核心，并将成本加起来(这很快)，然后查看是否有核心标志成功。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1022919|更一般地，NP中的问题是决策问题，使得可以在多项式时间内(即，有效地)验证潜在解，并且因此(由于潜在解是可枚举的)，任何这样的问题都可以用足够多的CPU有效地解决。|1022920|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

It sure is. Consider the Traveling Salesman Problem in it's strict NP form: given this list of costs for traveling from each point to each other point, can you put together a tour with cost less than K? With the new infinite-core CPU from Intel, you just assign one core to each possible permutation, and add up the costs (this is fast), and see if any core flags a success.

More generally, a problem in NP is a decision problem such that a potential solution can be verified in polynomial time (i.e., efficiently), and so (since the potential solutions are enumerable) any such problem can be efficiently solved with sufficiently many CPUs.

blocks|key|277694|text|听起来你真正想问的是O(n!)在非确定性机器上，复杂度可以降低到O(n%5Ea)；换句话说，是否-P=+NP。这个问题的答案是否定的，有些非P问题不是NP问题。例如，一个有限的停机问题(它询问一个程序是否最多在n！步骤)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|277695|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It sounds like what you're really asking is whether a problem of O(n!) complexity can be reduced to O(n^a) on a non-deterministic machine; in other words, whether Not-P = NP. The answer to that question is no, there are some Not-P problems that are not NP. For example, a limited halting problem (that asks if a program halts in at most n! steps).

blocks|key|2926642|text|问题将是分发工作和收集结果。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926643|如果所有CPU可以一次读取相同的存储器片段，并且如果每个CPU具有已知的唯一CPU-ID，则可以使用该ID来选择排列，并且分配问题可以在恒定时间内解决。|2926644|不过，收集结果将是一件棘手的事情。每个CPU可以与它的(数值)邻居进行比较，然后将结果与两个最近邻居的结果进行比较，等等。这将是一个O(log(n!))进程。我不确定，但我怀疑O(log(n!))是超多项式的，所以我不认为这是一个解决方案。|2926645|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

The problem would be distributing the work and collecting the results.

If all the CPUs can read the same piece of memory at once, and if each one has a unique CPU-ID that is known to it, then the ID may be used to select a permutation, and the distribution problem is solveable in constant time.

Gathering the results would be tricky, though. Each CPU could compare with its (numerical) neighbor, and then that result compared to the result of the two closest neighbors, etc. This will be a O(log(n!)) process. I don't know for sure, but I suspect that O(log(n!)) is hyperpolynomial, so I don't think that's a solution.

blocks|key|2926691|text|如果问题是检查复杂度为O(n!)的问题的排列/答案，那么您当然可以使用无限数量的处理器有效地完成这一任务。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926692|原因是，您可以轻松地以对数效率分发问题的原子部分(例如，问题的原子部分可能是要检查的排列之一)。|2926693|举个简单的例子，你可以把处理器设置成‘二叉树’。您可以在根本上，让处理器将问题的排列(或任何最小的问题部分)传递给叶处理器来解决，最终以log(n!)时间到了。|2926694|请记住，将排列传递到处理器需要很长时间。问题本身的每个部分实际上都会立即得到解决。|2926695|编辑:根据下面的评论修复了我的帖子。|2926696|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

If the problem is one of checking permutations/answers to a problem of complexity O(n!), then of course you can do it efficiently with an infinite number of processors.

The reason is that you can easily distribute atomic pieces of the problem (an atomic piece of the problem might, say, be one of the permutations to check) with logarithmic efficiency.

As a simple example, you could set up the processors as a 'binary tree', so to speak. You could be at the root, and have the processors deliver permutations of the problem (or whatever the smallest pieces of the problem might be) to the leaf processors to solve, and you'd end up solving the problem in log(n!) time.

Remember it's the delivery of the permutations to the processors that takes a long time. Each part of the problem itself will actually be solved instantly.

Edit: Fixed my post according to the comments below.

blocks|key|2926752|text|不，不！甚至比NP还要高。认为无限并行可以在多项式时间内解决NP问题，这通常被认为是一个“合理”的时间复杂度，N！在这样的设置下，问题仍然高于多项式。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926753|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

No, N! is even higher than NP. Thinking unlimited parallelism could solve NP problem in polynomial time, which is usually considered as a "reasonable" time complexity, N! problem is still higher than polynomial on such a setup.

blocks|key|2926791|text|你提到搜索是一个“典型”的问题，但你实际上被问到的是关于搜索问题的具体问题吗？如果是，那么搜索通常是可并行化的，但据我所知，O(n!)原则上并不意味着可并发性的程度，不是吗？你可以有一个完全连续的O(n!)问题，这意味着无限的计算机不会有帮助。我曾经遇到过一个不同寻常的O(n%5E4)问题，实际上是完全连续的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926792|所以，可用的并发性是第一件事，如果你在面试中提到Amdahl定律，我会给你加分。下一个潜在的陷阱是处理器间的通信，以及算法的性质。例如，考虑下面的应用程序类列表：http://view.eecs.berkeley.edu/wiki/Dwarf_Mine。FWIW我前面提到的O(n%5E4)代码有点属于FSM类别。|offset|length|2926793|另一个有点相关的轶事:我曾听一位来自超级计算机供应商的工程师声称，如果他们将10%25的CPU时间花在MPI库中，他们认为并行化是一个巨大的成功(尽管这可能仅限于计算化学领域的代码)。|2926794|entityMap|0|LINK|mutability|MUTABLE|url|http://view.eecs.berkeley.edu/wiki/Dwarf_Mine^0|0|29|19|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

You mentioned search as a "typical" problem, but were you actually asked specifically about a search problem? If so, then yes, search is typically parallelizable, but as far as I can tell O(n!) in principle does not imply the degree of concurrency available, does it? You could have a completely serial O(n!) problem, which means infinite computers won't help. I once had an unusual O(n^4) problem that actually was completely serial. 

So, available concurrency is the first thing, and IMHO you should get points for bringing up Amdahl's law in an interview. Next potential pitfall is inter-processor communication, and in general the nature of the algorithm. Consider, for example, this list of application classes: <a href="http://view.eecs.berkeley.edu/wiki/Dwarf_Mine" rel="nofollow noreferrer">http://view.eecs.berkeley.edu/wiki/Dwarf_Mine</a>. FWIW the O(n^4) code I mentioned earlier sort of falls into the FSM category. 

Another somewhat related anecdote: I've heard an engineer from a supercomputer vendor claim that if 10% of their CPU time were being spent in MPI libraries, they consider the parallelization a solid success (though that may have just been limited to codes in the computational chemistry domain).

blocks|key|1026843|text|这就好比在一台装有文字处理器的防破坏计算机上，有无限多只猴子在打字，能否在无限长的时间里写出莎士比亚的所有作品。现实主义者会说不是，因为条件在物理上是不可能的。理想主义者会说“是”；从理论上讲，这是可以发生的。既然软件工程(软件工程，而不是计算机科学)关注的是我们看得见摸得着的真实系统，那么答案是否定的。如果你怀疑我，那就去构建它，证明我是错的！我的天。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1026844|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

This is like asking if an infinite number of monkeys typing on a monkey-destruction proof computer with a word-processor can come up with all the works of Shakespeare; given an infinite amount of time. The realist would say not since the conditions are no physically possible. The idealist will say yes; in theory it can happen. Since Software Engineering (Software Engineering, not Computer Science) focuses on real system we can see and touch, then the answer is no. If you doubt me, then go build it and prove me wrong! IMHO.

blocks|key|2926903|text|有时正确的答案是，“你的代码库会出现多少次？”但在这种情况下，有一个真正的答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926904|正确的答案是否定的，因为并不是所有的问题都可以使用完美的并行处理来解决。例如，一个类似旅行推销员的问题必须致力于一条路径，才能考虑旅程的第二段。|2926905|假设有一个完全连接的城市矩阵，如果您想为疲惫的推销员显示所有可能的非循环路线，您将遇到一个O(n!)问题可以分解为O(n)*O((n-1)!)问题来了。问题是，在考虑其余路径(在O((n-1)!)上)之前，您需要提交一条路径(在等式的O(n)一侧)。等式的一侧)。|2926906|由于某些计算必须在其他计算之前执行，因此无法在单个散布/聚集过程中完美地分散结果。这意味着解决方案将等待计算的结果，计算结果必须在“下一步”开始之前出现。这是关键，因为对先前部分解决方案的需要在继续进行计算的能力方面提供了一个“瓶颈”。|2926907|因为我们已经证明我们可以让许多这样的CPU等待(即使它们自己在等待)，所以我们知道运行时不能是O(1)，我们只需要选择一个非常大的N来保证一个“不可接受”的运行时间。|2926908|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Sometimes the correct answer is, "How many times does this come up with your code base?" but in this case, there is a real answer.

The correct answer is no, because not all problems can be solved using perfect parallel processing. For example, a travelling salesman-like problem must commit to one path for the second leg of the journey to be considered.

Assuming a fully connected matrix of cities, should you want to display all possible non-cyclic routes for our weary salesman, you're stuck with a O(n!) problem, which can be decomposed to an O(n)*O((n-1)!) problem. The issue is that you need to commit to one path (on the O(n) side of the equation) before you can consider the remaining paths (on the O((n-1)!) side of the equation).

Since some of the computations must be performed prior to other computations, then there is no way to scatter the results perfectly in a single scatter / gather pass. That means the solution will be waiting on the results of calculations which must come before the "next" step can be started. This is the key, as the need for prior partial solutions provide a "bottle neck" in the ability to proceed with the computation.

Since we've proven we can make a number of these infinitely fast, infinitely numerous, CPUs wait (even if they are waiting on themselves), we know that the runtime cannot be O(1), and we only need to pick a very large N to guarantee an "unacceptable" run time.

blocks|key|1517972|text|不考虑设置的成本(例如，任何可能向处理单元发送(+be...assigning+)一系列值的东西)，则是。在这种情况下，任何小于无穷大的值都可以在相同数量的处理单元上的一次并发迭代中求解。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1517973|然而，设置是一件重要的事情，需要忽略。|1517974|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Disregarding the cost of setup (whatever that might be...assigning a range of values to a processing unit, for instance), then yes. In such a case, any value less than infinity could be solved in one concurrent iteration across an equal number of processing units. 

Setup, however, is something significant to disregard.

blocks|key|2926732|text|每个问题都可以通过一个CPU来解决，但是谁会将这些作业分发给所有无限的CPU呢？一般来说，这个任务是集中的，所以如果我们有无限的任务要交付给所有无限的CPU，我们可能会花费无限的时间来完成。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2926733|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Each problem could be solved by one CPU, but who would deliver these jobs to all infinite CPU's? In general, this task is centralized, so if we have infinite jobs to deliver to all infinite CPU's, we could take infinite time to do so.

Is it possible to solve a problem of O(n!) complexity within a reasonable time given infinite number of processing units and infinite space? 

The typical example of O(n!) problem is brute-force search: trying all permutations (ordered combinations).

The limits of parallelism (job-interview question)

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

是否有可能解决O(n!)在给定无限数量的处理单元和无限空间的情况下，在合理的时间内实现复杂度？O(n!)问题是暴力搜索:尝试所有的排列(有序组合)。

问并行的极限(求职面试问题)
EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问并行的极限(求职面试问题)EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问并行的极限(求职面试问题)
EN