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.
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.