Well, running a Turning machine for time t can be simulated by a circuit of size O(t2), so in terms of efficiency it’s much closer to “doing search” than to “memorizing the output of search”.
So if a search takes time exponential in the input size, the search-simulating circuit is size O(et)… and if memorizing the answers also requires circuit length exponential in input size, they’re roughly tied.
So the line where minimal circuits start memorizing rather than running is around there. Any search type worse than exponential, and it’ll memorize; anything better, and it won’t.
Well, running a Turning machine for time t can be simulated by a circuit of size O(t2), so in terms of efficiency it’s much closer to “doing search” than to “memorizing the output of search”.
OK.
So if a search takes time exponential in the input size, the search-simulating circuit is size O(et)… and if memorizing the answers also requires circuit length exponential in input size, they’re roughly tied.
So the line where minimal circuits start memorizing rather than running is around there. Any search type worse than exponential, and it’ll memorize; anything better, and it won’t.