3 added 97 characters in body

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.

2 added 398 characters in body

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

1

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.

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