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