Link to original article

Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: ELK Computational Complexity: Three Levels of Difficulty, published by Abram Demski on March 30, 2022 on The AI Alignment Forum. ELK is described as a problem we wish to solve in the "worst case"; IE, for any potential failure case we can describe, we want to have a strong argument about why we won't run into that particular problem. The ELK document lists several cases we want to handle in that way. First in this list is the case where the correct translation is arbitrarily computationally complex. However, this assumption implies that ELK is intractable. At best, we might hope to define some notion of approximate solution, and prove that there are efficient approximate solutions. So how are we supposed to solve ELK, if we are to assume that it's intractable? The answer (at least, as I see it) is by arguing that the correct translation cannot be too computationally complex. (Or, failing that, by providing a strong argument that it is possible, at which point we would have to narrow the scope of ELK ambitions.) A proposed algorithm for solving ELK which (1) has a strong argument for its correctness, and (2) is itself a tractable algorithm, is usually already an argument that correct translations are tractable. For example, a search procedure usually has to evaluate candidate translations by running them; so if we could prove that the search terminates in a reasonable amount of time, we've probably already proven that the solution it finds is tractable (at least in certain cases, EG, on the training data). But this doesn't really answer the question. Since we don't already have such a solution, we may need to explicitly think about tractability in order to produce one. So, in this post, I'm going to think about how we might possibly bound the computational complexity of ELK. Level 3: Probabilistic Knowledge The third level of difficulty for ELK (IE, the most computationally difficult that I'll discuss here) is the most conceptually simple to understand: we define the "correct translation" of a pattern of activity in the Predictor to be any and all things correlated with such activity. In other words, we define the "meaning" of Predictor activity as just whatever we can predictably infer from it. In my previous post I formalized this by imagining probability distributions called "third person perspectives" which can be conditioned on the full execution trace of the Predictor, and infer as much as possible about the world from this information. This seems intractable for two main reasons: It requires logical omniscience. For example, this criterion seemingly requires that the correct translation knows all the predictable consequences of a plan, not just the immediate consequences. So long as the consequences can be predicted by running the world-model forward, they count as probabilistic implications of the Predictor's knowledge. In particular, the future outcomes of any computations running in the world are included in this. Therefore, computing this form of ELK requires access to a halting oracle in the worst case. Even if we can side-step the first issue, this form of ELK is at least as hard as finding marginals in arbitrary graphical models, which is #P-complete. As complexity classes go, this is worse than NP-complete. By trying to detect any correlation, we impose an arbitrarily high requirement of detailed simulation. As a consequence, this Reporter would know far more than the Predictor can realistically be said to know. If the Predictor knows how the dominoes have been set up, the Reporter is required to know how they fall. From a safety perspective, we're fine with the reporter knowing too much -- we're only concerned with cases where the Predictor knows something which the humans don't know. However, this does seem like a sign that we don't have to solve such...