[kazinator]

The complexity topic from which we have P = NP is not actually about time, but number of steps.

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.

If you have access to unlimited parallelism, then, for instance, some recursive algorithms that completely process a tree structure can drop from linear time to logarithmic.

[lisper]

> 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.

[kazinator]

For sufficiently large N, all computation that isn't O(1) takes infinite time.

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.

[medo-bear]

> Sorry to be the one to break this to you but you live in a finite universe

i don't think cosmologists make that claim in such a strong way. its mainly worded something along the lines of, "given our current understanding, its most likely to be finite"

[lisper]

"You live in a finite universe" is not the same as "the universe is finite". You live in a light cone, and unless you are immortal that light cone comprises a finite amount of space-time.

[medo-bear]

> "You live in a finite universe" is not the same as "the universe is finite".

it is if the word 'universe' designates the same thing. otherwise what you want to say is "your experience of the universe is finite"

[lisper]

OK, whatever. The point is you cannot possibly access unlimited parallelism.