Is it possible (slash can you provide an example) to reduce computational complexity of a problem by using a parallel algorithm which does not require a number of processors relative to the input size?
There is an emerging field of coarse-grained parallel algorithms, where the running time (and other computational resource consumption) is regarded as a function of independent parameters n (input size) and p (number of processors), often under a natural assumption n >> p.
A good starting point is to google for "bulk-synchronous parallelism".
You might be interested in this paper:
He provides examples of computational problems in which "the sequential solution is more than $n$ times slower than an $n$-processor parallel solution"; this is done by creatively interpreting the concept of a "computational problem".
If you distribute the task to $p$ (where $p$ is a constant) processors.
Then complexity may be $O(f(n)/p) \rightarrow O((1/p)f(n)) \rightarrow O(cf(n)) \rightarrow O(f(n))$ where $c=1/p$.
What we use parallelism is to reduce run-time of the task i.e. if a task is taking $T$ seconds then with parallelism it may take $T/p + SomeMoreTime$.
But NO complexity change.
"you can't compute it with 1 processor, but can compute with 2."
This is not possible, assuming that both processors are TMs or a less powerful model. From wikipedia , for multi-tape machines :
This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how large the k, can be simulated by a single-tape machine using only quadratically more computation time (Papadimitriou 1994, Thrm 2.1)
Also for multi-head machines, from "Linear time simulation of multihead turing machines with head — To-head jumps" by Walter J. Savitch and Paul M. B. Vitányi :
The main result of this paper shows that, given a Turing machine with several read-write heads per tape and which has the additional one move shift operation "shift a given head to the position of some other given head", one can effectively construct a multitape Turing machine with a single read-write head per tape which simulates it in linear time; i.e. if the original machine operates in time T(n), then the simulating machine will operate in time cT(n), for some constant c.
Perhaps "parallel or" (given two functions returning a boolean, tell whether one of them returns true, given that any of them, but not both, might fail to terminate) might be what you're talking about: you can't compute it with 1 processor, but can compute with 2.
However, this much depends on which computational model you'll be using, whether you're given the processes as black boxes or as their description which you can interpret yourself, etc.