Andrey Kolmogorov, Fred Hennie, Richard Stearns, and Walter Savitch are all famous separately; but they have something in common. Read on, and see. Today I wish to discuss some algorithmic tricks and show that they were initially used by complexity theorists, years before they were used by algorithm designers. To steal a phrase: it`s computational complexity all the way down. Well not exactly. The situation is slightly more complex”a bad pun. The complexity theorists often invented a concept and used it in a narrow way, while later it was rediscovered and made a general notion.

» Dick Lipton |