Complexity theory literature is littered with algorithms that rely on things like O(1) access to a 2^O(n)-sized array. They are almost uniformly wildly impract

Complexity theory literature is littered with algorithms that rely on things like O(1) access to a 2^O(n)-sized array. They are almost uniformly wildly impractical. In fact, even 2^O(w) (where w is the word size in bits), which you see sometimes in the succinct data structures literature on stuff like optimal compression of bit vectors, is usually unusable because the asymptotic improvement doesn't kick in until w = 128 or whatever. As another illustrative example, if you allow unbounded fan-in and an exponential number of AND/OR gates, you can solve any monotone boolean function in two steps (you just take the DNF of a positive input and turn it into a circuit). This means that if you're willing to use an unbounded amount of space (chip area, in this case), you can simulate things like k-clique for any fixed k < n in two steps. As a result, essentially all circuit lower bound results either restrict fanin (to 2, generally) or restrict you to polynomial chip area. Moreover, you can encode any monotone boolean function of n inputs in O(lg(Dedekind(n))) bits as long as you have an auxiliary array of size O(Dedekind(n)), which you can look up answers in in constant time. So you can compress boolean functions pretty well (about 5x more than the naive bit lookup solution for n=32), but Dedekind(n) grows so fast that nobody would ever actually try to implement this. I have lots more examples, if you want them :P Exponential space algorithms are almost totally useless in nearly all cases (with the exception of those that only rarely take exponential space).