Studying for my qualifying exam, have a past exam here, which has the following question, verbatim:

Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the space used by a sequential algorithm for a problem $X$ can be equated (within Big Oh) to the time taken by a parallel algorithm for $X$.

However, in the textbook I have, I haven't found a good definition for a sequential algorithm or parallel algorithm, which is necessary if I'm going to prove anything. Also, googling turned up the wikipedia page on parallel computation thesis but it seems to depend on the model of computation used. So I'm not sure how to answer this question.

  • $\begingroup$ I agree: this question is ill-posed without context, and does not admit an answer. It seems clear this this is a question about complexities of problems, not cost of algorithms. $\endgroup$ – Raphael Mar 6 '15 at 6:57

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.