0
$\begingroup$

Consider the following algorithm:

  1. run algorithm A until a solution or out of memory
  2. 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:

  1. run algorithm A' until a solution or out of memory
  2. 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.

My questions:

  • 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"?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.