Consider the following algorithm:
- run algorithm A until a solution or out of memory
- run algorithm B
Then if A does not solve the problem, a computer with less memory has an advantage.
This could be solved by running A and B in parallel, but then the resulting parallel algorithm could be renamed A' and run:
- run algorithm A' until a solution or out of memory
- run algorithm B'
for some algorithm B', possibly producing a similar result (out of memroy is an advantage).
Also, more generally, if an algorithm goes in a wrong direction, a weaker computer has an advantage.
- Could you describe systematically such cases when weaker computers have advantage?
- Could you refer to some articles or books (preferrably open access) on this topic?
- What's about a generic solution of this "trouble"?