Limits to Parallel Computing
A friend just asked me, if for every problem that takes time t on one processor, solving it on two processors will take t/2. Obviously, this is not known in the general case.
Is there a counter examples to this? Meaning, is there a problem that is provably "hard to parallel"?