The limits of parallelism

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

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

I have asked this question on Stackoverflow, but it seems to be more appropriate to ask it here.

• You may want to see en.wikipedia.org/wiki/NC_(complexity) Mar 30 '10 at 12:54
• @rgrig: thanks, I know already well enough about NP theory :) Mar 30 '10 at 13:07
• I didn't link to NP. Roughly, problems in NC are those that can be done really fast with many processors. It's not really an answer to what you ask, because the polylog time is low enough to make NC not bigger than P. You probably want something like PT/WK(poly,poly), but I don't know much about such a complexity class. Mar 30 '10 at 13:37
• In other words, I think a better question would be along the lines: "Which problems can be solved in deterministic worst-case poly time given a poly number of processors on a PRAM machine?" Mar 30 '10 at 13:41
• @rgrig: I don't think this is what psihodelia is asking. Any problem solvable by a polynomial number of processors in deterministic polynomial time already lies in P, which is properly contained in EXPTIME $\subset$ TIME(n!). I think the question is whether you can solve any problem in TIME(n!) using an arbitrary number of processors (say n! of them), in deterministic polynomial time.
– AVS
Mar 30 '10 at 14:23

As a general rule, parallel time complexity classes are closely related to serial space complexity classes. A standard result (see Sipser or Papadimitriou) is $${\rm\bf PT/WK}\bigl(f(n),k^{f(n)}\bigr)\subseteq {\rm\bf SPACE}(f(n))\subseteq{\rm\bf NSPACE}(f(n))\subseteq{\rm\bf PT/WK}\bigl(f(n)^2,k^{f(n)^2}\bigr),$$ where ${\rm\bf PT/WK}\bigl(f(n),g(n)\bigr)$ is the class of problems that can be solved in $f(n)$ time with $g(n)$ total work (sum of the times over all processors).

So if we impose a space restriction, say we consider a problem in ${\rm\bf TIME}(n!)\cap{\rm\bf SPACE}(n^k)$, then this problem also lies in ${\rm\bf PT/WK}\bigl(n^{2k},k^{n^{2k}}\bigr)$ and the answer to your question is yes.

Without any space restriction, I believe the answer to your question is unknown. It is analogous to asking whether ${\rm\bf P}$ is contained in ${\rm\bf NC}$. We know ${\rm\bf NC}\subseteq{\rm\bf P}$, so this amounts to the open question ${\rm\bf NC} = {\rm\bf P}$?

I would have put this as a comment but it went over the character limit...

Honestly, the question is ill-formed. It really cannot be answered accurately without knowing more about what parallel computational model the questioner has in mind. Since the questioner brought up "trying all possible permutations", it sounds like they want to simulate arbitrary $\mathbf{TIME-SPACE}(n!, n \log n)$ computations, or maybe even $\mathbf{NTIME}[n \log n]$ computations, not $\mathbf{TIME}(n!)$ computations.

At any rate, without further knowledge of the computational model, the answer could be "yes" even in the hardest case, $\mathbf{TIME}(n!)$. For instance, suppose you allow $2^{O(poly(n!))}$ different processors to generate all possible strings of length $O(poly(n!))$, assigning one string to every processor. (The notation $poly(n)$ just denotes a bound of the form $O(n^c)$ for a fixed constant $c > 0$.) Let each processor treat its given string as a potential probabilistically checkable proof of the $\mathbf{TIME}(n!)$ computation, then have the processor verify this proof in randomized $O(poly(n))$ time, querying at most $O(poly(n))$ bits of the potential proof. If a processor accepts its proof then it tries to write "1" in a global memory location, otherwise it does not try to write. Another processor just runs in polynomial time polling that location to see if "1" ever gets written. Under some complexity measures, this whole device would run in polynomial time. However it takes $2^{O(poly(n!))}$ processors to do it.

The probabilistically checkable proof could even be replaced with $O(poly(n!))$ more "sub-processors" assigned to each processor. The processor would treat its $O(poly(n!))$ string as a valid computation history of the machine. Have each sub-processor check the correctness of some $O(1)$ bits of the computation history, and send a "1" to its processor if it finds those bits to be correct. Finally, if all sub-processors send "1" to the processor, then the processor writes "1" in the global memory location. This would require that the processor can check the AND of $O(poly(n!))$ bits in $O(poly(n))$ time, but maybe this is within the bounds of what the questioner will allow.

The general consensus here is that a problem can't be solved efficiently in parallel unless it can be solved efficiently by a single computer. Imagine instead of having n computers working on a problem for X time you gave one computer n*X time. Without factoring in the overhead of communication, you can get an n times speedup by using n processors.

Since you are asking about an infinite number of processors, you're asking a question which is equivalent to what a single computer can compute if we don't concern ourselves with time at all. This question got its first few answers from Kleene, Godel, Turing and several other giants. We still don't know everything that a computer can and can not compute to this day - but we do know some things that can not be computed (like the Halting Problem) even with infinite parallel computation.

For the record, if your limitation is infinite processors for an O(n!) problem, I could assign each of the processors to compute one single permutation each and have plenty of computers to spare [;-)]. What we're really interested in is knowing what's computable in an efficient amount of time and an efficient amount of physical resources.

• We don't know that every problem in TIME(n!) can necessarily be solved by checking n! cases in parallel. The key question here is whether there exist problems that are "inherently sequential" (i.e. can't be sped up with parallelism). This question is essentially orthogonal to the question of what can be computed efficiently.
– AVS
Mar 30 '10 at 19:00
• Oh okay. I misunderstood. I have an anecdotal example then... physical calculations can be done in parallel but only to a certain extent. Each "state" of a physical system depends on the full configuration of the previous state. There is a way to encode the partition problem (NP-Complete) into a physics calculation of electron spins in an infinite-range antiferromagnet [due to Stephan Mertens]. Mar 31 '10 at 20:15
• While each state of the evolving system might be computed in parallel, physical systems can only be computed in parallel and the amount of time it takes for the electron calculations in the antiferromagnet to settle take time exponential in the base (as would be expected). Of course this doesn't count as a proof until we are certain that physics computations DO require serial computations. Right now we only have good reason to believe. Mar 31 '10 at 20:15