3 ms·

Somewhat off topic, and I ask out of genuine curiosity - when did the “this computation will take sifting through more combinations than there are visible atoms

Somewhat off topic, and I ask out of genuine curiosity - when did the “this computation will take sifting through more combinations than there are visible atoms in the universe” meme emerge? I’ve never quite understood why that’s an important metric for considering processing. Does it have an actual impact on the computability of something, or is it just a visualisation to help human minds scale the grasp of something?

bmc7505 5y ago
We don't have the words to describe how quickly these nonlinear recurrence relations grow. Many program synthesis problems are essentially super-exponential. Look at the Ackermann function, which describes the complexity of many decidable algorithms as you increase problem size -- it's a different kind of scaling altogether.
rank0 5y ago
It’s a pretty useful concept when you consider cryptography. The idea that enumeration is mathematically infeasible for some set is the basis for many cryptographic functions. But basically yeah it’s just an illustration of the difficulty. Obviously we’ll never have a supercomputer’s worth of computing power for every atom.
kragen 5y ago
I prefer "sifting through more combinations than there are elementary particles in the universe times the universe's age in picoseconds"; it's a fairly reliable indicator that exhaustive search is not a viable way to solve the problem, not just today but, with classical computing, ever, because it's very unlikely that we can make a working computer out of less than a single elementary particle, try more than one guess per picosecond (per computer), or wait longer than the current age of the universe for an answer. I've seen such calculations at least since the 01990s. It might turn out to be wrong (for example, elementary particles or black holes might have exploitable structure, a picosecond is pretty long compared to the Planck time, or closed timelike curves in spacetime might allow you to spend an unboundedly long time computing something), but at the very least it's a strong suggestion that exhaustive search will not be fruitful. For more immediate purposes I prefer the dollar cost of carrying out the computation with currently available hardware. Quantum computing, when it becomes practical, will give you only a quadratic speedup, as far as we know. So the relevant problem size then expands to the square of the number above.
- codeisawesome 5y ago
  I definitely like the metric as better fitting, once multiplied by time! Thanks for sharing!

bmc7505 5y ago

We don't have the words to describe how quickly these nonlinear recurrence relations grow. Many program synthesis problems are essentially super-exponential. Look at the Ackermann function, which describes the complexity of many decidable algorithms as you increase problem size -- it's a different kind of scaling altogether.

rank0 5y ago

It’s a pretty useful concept when you consider cryptography. The idea that enumeration is mathematically infeasible for some set is the basis for many cryptographic functions. But basically yeah it’s just an illustration of the difficulty. Obviously we’ll never have a supercomputer’s worth of computing power for every atom.

kragen 5y ago

I prefer "sifting through more combinations than there are elementary particles in the universe times the universe's age in picoseconds"; it's a fairly reliable indicator that exhaustive search is not a viable way to solve the problem, not just today but, with classical computing, ever, because it's very unlikely that we can make a working computer out of less than a single elementary particle, try more than one guess per picosecond (per computer), or wait longer than the current age of the universe for an answer. I've seen such calculations at least since the 01990s. It might turn out to be wrong (for example, elementary particles or black holes might have exploitable structure, a picosecond is pretty long compared to the Planck time, or closed timelike curves in spacetime might allow you to spend an unboundedly long time computing something), but at the very least it's a strong suggestion that exhaustive search will not be fruitful. For more immediate purposes I prefer the dollar cost of carrying out the computation with currently available hardware. Quantum computing, when it becomes practical, will give you only a quadratic speedup, as far as we know. So the relevant problem size then expands to the square of the number above.

codeisawesome 5y ago
I definitely like the metric as better fitting, once multiplied by time! Thanks for sharing!