This is not true in the circuit-depth complexity model. Remember that an arbitrary lookup table is O(log n) circuit depth. If my function I’m trying to memorize is f(x) = (x & 1), the fastest circuit is O(1), whereas a lookup table is O(log n).
Certainly, I’m assuming that the intended function is not in O(log n), though I think that’s a very mild assumption for any realistic task.
I think the prior you’re suggesting is basically a circuit size prior. How do you think it differs from that?
Certainly, I’m assuming that the intended function is not in O(log n), though I think that’s a very mild assumption for any realistic task.
In t time, the brain (or any realistic agent) can do O(t) processing… but receives O(t) sensory data.
I think the prior you’re suggesting is basically a circuit size prior. How do you think it differs from that?
Realizable-speed priors are certainly correlated with circuit size priors to some extent, but there are some important differences:
The naive circuit size prior assumes gates take O(1) space and wiring takes zero space, and favors circuits that take less space.
There are more complex circuit size priors that e.g. assign O(1) space to a gate and O(length) space to wiring.
The O(log(n)) variant of the realizable-speed prior has no simple analog in the circuit size prior, but roughly corresponds to the circuit-depth prior.
The O(n1/2) variant of the realizable-speed prior has no simple analog in the circuit size prior.
The O(n1/3) variant of the realizable-speed prior roughly corresponds to the complex circuit-size prior described above, with differences described below.
Circuit size priors ignore the effects of routing congestion.
A circuit-size prior will prefer one complex circuit of N-1 gates over two simpler circuits of N/2 gates.
A realizable-speed prior will tend to prefer the two simpler circuits, as, essentially, they are easier to route (read: lower overall latency due to shorter wiring)
My (untested) intuition here is that a realizable-speed prior will be better at structuring and decomposing problems than a circuit-size prior, as a result.
Circuit size priors prefer deeper circuits than realizable-speed priors.
A circuit-size prior will prefer a circuit of max depth 10D and N gates over a circuit of max depth D and N-1 gates.
A realizable-speed prior will (typically) prefer the slightly larger far shallower circuit.
Note that the human brain is surprisingly shallow, when you consider speed of neuron activation versus human speed of response. But also very wide...
Certainly, I’m assuming that the intended function is not in O(log n), though I think that’s a very mild assumption for any realistic task.
I think the prior you’re suggesting is basically a circuit size prior. How do you think it differs from that?
In t time, the brain (or any realistic agent) can do O(t) processing… but receives O(t) sensory data.
Realizable-speed priors are certainly correlated with circuit size priors to some extent, but there are some important differences:
The naive circuit size prior assumes gates take O(1) space and wiring takes zero space, and favors circuits that take less space.
There are more complex circuit size priors that e.g. assign O(1) space to a gate and O(length) space to wiring.
The O(log(n)) variant of the realizable-speed prior has no simple analog in the circuit size prior, but roughly corresponds to the circuit-depth prior.
The O(n1/2) variant of the realizable-speed prior has no simple analog in the circuit size prior.
The O(n1/3) variant of the realizable-speed prior roughly corresponds to the complex circuit-size prior described above, with differences described below.
Circuit size priors ignore the effects of routing congestion.
A circuit-size prior will prefer one complex circuit of N-1 gates over two simpler circuits of N/2 gates.
A realizable-speed prior will tend to prefer the two simpler circuits, as, essentially, they are easier to route (read: lower overall latency due to shorter wiring)
My (untested) intuition here is that a realizable-speed prior will be better at structuring and decomposing problems than a circuit-size prior, as a result.
Circuit size priors prefer deeper circuits than realizable-speed priors.
A circuit-size prior will prefer a circuit of max depth 10D and N gates over a circuit of max depth D and N-1 gates.
A realizable-speed prior will (typically) prefer the slightly larger far shallower circuit.
Note that the human brain is surprisingly shallow, when you consider speed of neuron activation versus human speed of response. But also very wide...