Why Adding a Full Hard Drive Can Make a Computer More Powerful

In the late 2000s, McKenzie and the pioneering complexity theorist Stephen Cook devised a problem that seemed like a promising candidate. Called the tree evaluation problem, it involves repeatedly solving a simpler math problem that turns a pair of input numbers into a single output. Copies of this math problem are arranged in layers like the matches in a tournament bracket: The outputs of each layer become the inputs to the next layer until there’s just one output remaining. Different tree evaluation algorithms represent different strategies for calculating this final output from the initial inputs—they might perform the calculations in a different order, or record the results of intermediate steps in a different way. Many algorithms can solve the tree evaluation problem quickly, putting it in the class P. But every such algorithm must devote some memory to the numbers it’s working with, while also storing numbers it’s already calculated for use in later steps. That’s why Cook and Mc ... Read full article.