This action will delete this post on this instance and on all federated instances, and it cannot be undone. Are you certain you want to delete this post?

Delete This Post

This action will delete this post on this instance and on all federated instances, and it cannot be undone. Are you certain you want to delete this post?

toddsundsted postedOct 6, 2021

thinking about this: complexity has to live somewhere

complexity has to live somewhere—the trick is putting it in the right place. modern cpus are incredibly complex: multiple tiers of caching, speculative execution, etc. none of which you ever think about when building a web app, which in turn has its own kind of complexity.

a cpu runs on top of some very complex and speculative physics that we only incompletely understand: neutrino oscillations, quark color confinement... luckily you also don’t need to understand any of that when building a web app. 😀

my 2¢ is, put as much complexity as is necessary *inside* of a microservice, framework or library—as long as the team that maintains it can understand it. but make its interface as simple as possible, so that the team at large can effectively make use of it.

it’s kind of the opposite of worse is better, but i think the use case is different.

toddsundsted postedMar 7, 2021

I recently stumbled across Scott Aaronson's lecture notes for PHYS771 Quantum Computing Since Democritus. (I haven't yet read the book.)

Scott Aaronson is a computational complexity researcher/thinker first and foremost, and I love his particular style/peculiar style. En route to quantum computing, he talks a lot about computational complexity, reflects on free will, and manages to loop in time travel, as he does. But the notes (and presumably the book) are not a primer on quantum computing (which was what I was looking for).

The questions Scott’s trying to answer are, generally, *what kind of problems can you solve with quantum computing*, and, specifically, *will we be able to solve NP complete problems in polynomial time with quantum computing*. These are *very important* questions, because Shor’s algorithm (a quantum algorithm) can factor integer primes in polynomial time, which threatens to reduce the effectiveness of a lot of the cryptography on which we all depend. So there are real world consequences.

Factoring integer primes is in NP but it's not known/believed to be NP complete, but if a polynomial time algorithm is discovered for a known NP complete problem, like the traveling salesperson problem, an entire class of difficult problems becomes very much easier to solve, because a solution for one NP complete problem is a solution for any NP complete problem.

How much easier? For reasonably large problems it's the difference between solvable and solvable but not in the lifetime of the universe, because the only known algorithm amounts to trying every possible solution.