complexity theory

Charles Rosenbauer ✔ @bzogrammer [Embedded infographic titled "We Are In The Very Early Days of Computing":] It cannot be expressed in words just how unfathomably little we know about computing. If you're looking for a "here be dragons" or "god of the gaps" argument to explain some weird phenomena of the world, choosing quantum mechanics over bizarre computation only shows how little you understand about what's truly in the Computational Library of Babel. There are more possible programs that can be fit into a mere 32 bytes of data than there are atoms in the observable universe. We know NOTHING about what computers can truly do, and we could innovate in software until the last stars burn out and would still know ABSOLUTELY NOTHING. [Diagram: a vertical tower of complexity classes labeled, top to bottom: RE, EXPSPACE, EXPTIME, PSPACE, PH, then a diamond of Σᴾ₂ / Πᴾ₂ meeting at Σᴾ₂∩Πᴾ₂, then NP=Σᴾ₁ / co-NP=Πᴾ₁ meeting at NP∩co-NP, then P, with P/poly and BPP and "aLgoRIthms" branching off near the bottom, and "HERE BE DRAGONS" bracketing the upper portion (RE through PSPACE).] Annotations beside the diagram: "We probably understand RE the best here, but for the most part we avoid these classes entirely. We know almost nothing about what's out here." "Even then, by 'understand', I mostly mean that we've spent time understanding the properties of the weirdest stuff in RE. As for what kinds of useful things you can do with it, I guess we have interpreters, computers themselves, and a few other things, but this is mostly unexplored. We've largely scared ourselves off from exploring this seriously." "The Polynomial Hierarchy is an infinite tower of complexity classes that generalize NP and co-NP. We know there's a ton of weird stuff here, but it's almost entirely unexplored because programmers are deathly afraid of nondeterministic algorithms and anything that runs slower than quasi-linear time." "To say that we know more about space or the bottom of the ocean than we know about anything here is a vast understatement." "WEIRD stuff starts happening here. If you read old schizo Cybernetics stuff where Wiener or McCulloch start applying information theory and differential equations to understanding biology, sociology, or theology, a lot of the stuff they're doing lands here in NP. Even then, it's generally in only the most primitive corners of NP and Cybernetics was largely dead by the time we actually started understanding how weird NP really is." "Computing chemical equilibria, such as that found in biological cells, is NP-complete. The 'complete' part means that it can emulate anything in this entire complexity class, as well anything below." "Programmers will occasionally venture here, but generally are deathly afraid of it." ">99% of human-written code is in a tiny subset of this. If you have a rigid model of what 'algorithms' are and the kinds of properties they have, it's entirely because you're constrained to this tiny, well-behaved complexity class. Even then, we generally stick to the tiniest, easiest parts of it." 3:59 PM · Feb 21, 2026 · 10.4K Views