Reducing complexity with parallelism
If you mean O(1) processors, then no, computation complexity cannot be reduced.

Simply line up the work done by each processor and do it on a single one. If you are worried about synchronization, then one processor can easily emulate that.