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.)
That is a pretty cool idea.
There are a few like it. For example: All problems are at least Ω(max(N,M)), in the size of the problem description and output description.
It’s not usually the limiting factor. ;)
Actually, only the output; sometimes you only need the first few bits. Your equation holds if you know you need to read the end of the input.
And technically you can lower that to sqrt(M) if you organize the inputs and outputs on a surface.
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.)