True, but it’s a minimal circuit. When I wrote the remark, I was thinking: a minimal circuit will never do search; it will instead do something closer to memorizing the output of search (with some abstractions to compress further, so, not just a big memorized table). So I thought of the point of your counterexample as: “a minimal circuit may not do search, but it can implement the same policy as an agent which does search, which is exactly as concerning.”
I agree this isn’t really clear. I’ll revise the remark.
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.
True, but it’s a minimal circuit. When I wrote the remark, I was thinking: a minimal circuit will never do search; it will instead do something closer to memorizing the output of search (with some abstractions to compress further, so, not just a big memorized table). So I thought of the point of your counterexample as: “a minimal circuit may not do search, but it can implement the same policy as an agent which does search, which is exactly as concerning.”
I agree this isn’t really clear. I’ll revise the remark.
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.