[gwern]

Parallelization is a constant factor. If you have 1000 processors, you get a constant-factor one-time speedup of 1000x (or less). No complexity class changes.