|
|
|
|
|
|
by lisper
1367 days ago
|
|
|
> Of course that matters physically because if you only have a machine that performs one step at a time (or a somewhat better one that performs N steps at a time, for some fixed N), then the number of steps does translate to amount of time. It's much more fundamental than that. If you have any finite machine then the amount of time it takes to perform N steps will be proportional to N for sufficiently large N. > If you have access to unlimited parallelism... And if you had some magic pixie dust... Sorry to be the one to break this to you but you live in a finite universe. |
|
|
Complexity analysis goes out to infinity, but the way we use it as a tool is to inform us about what happens with our practical, finite inputs.
We know that something requires a non-polynomial number of steps, it quickly becomes untractable for small inputs. (So if we code that in a practical program, we need some justification that either the inputs won't occur, or we actively guard against them.)
Whether the entire universe is actually finite is not known, and not really relevant because that subset of it which is available to us as resources is vastly tiny.
The universe is vast, and vastly parallel: things are happening all over it at once, with more objects than have ever been crammed into any of our computing machines.