When we talk about the complexity of an algorithm, we have to decide what resources we are going to measure. Time used by a multi-tape Turing machine is the most common measurement, since it’s easy to define and generally matches up with physical time. If you change the model of computation, you can lower (or raise) this to pretty much anything by constructing your clock the right way.
Ah, sorry, I might not have been clear. I was referring to what may be physically feasible, e.g. a 3D circuit in a box with inputs coming in from the top plane and outputs coming out of the bottom plane. If you have one output that depends on all N inputs and pack everything as tightly as possible, the signal would still take Ω(sqrt(N)) time to reach. From all the physically doable models of computation, I think that’s likely as good as it gets.
Oh I see, we want physically possible computers. In that case, I can get it down to log(n) with general relativity, assuming I’m allowed to set up wormholes. (This whole thing is a bit badly defined since it’s not clear what you’re allowed to prepare in advance. Any necessary setup would presumably take Ω(n) time anyways.)
When we talk about the complexity of an algorithm, we have to decide what resources we are going to measure. Time used by a multi-tape Turing machine is the most common measurement, since it’s easy to define and generally matches up with physical time. If you change the model of computation, you can lower (or raise) this to pretty much anything by constructing your clock the right way.
Ah, sorry, I might not have been clear. I was referring to what may be physically feasible, e.g. a 3D circuit in a box with inputs coming in from the top plane and outputs coming out of the bottom plane. If you have one output that depends on all N inputs and pack everything as tightly as possible, the signal would still take Ω(sqrt(N)) time to reach. From all the physically doable models of computation, I think that’s likely as good as it gets.
Oh I see, we want physically possible computers. In that case, I can get it down to log(n) with general relativity, assuming I’m allowed to set up wormholes. (This whole thing is a bit badly defined since it’s not clear what you’re allowed to prepare in advance. Any necessary setup would presumably take Ω(n) time anyways.)