= 27d567bc2d48d9f40e9ccc20ea370b15)
endoself comments on Why AI may not foom - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (78)
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.)