The limits of parallelism (job-interview question)

Question

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).

Answer 1

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.