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:Alignment proposals and complexity classes, published by Evan Hubinger on the AI Alignment Forum. In the original “AI safety via debate” paper, Geoffrey Irving et al. introduced the concept of analyzing different alignment proposals from the perspective of what complexity class they are able to access under optimal play. I think this is a pretty neat way to analyze different alignment proposals—in particular, I think it can help us gain some real insights into how far into the superhuman different systems are able to go. Thus, the goal of this post is to try to catalog different alignment proposals based on the metric of what complexity class they have so far been proven to access. To do that, I have included a variety of new complexity class proofs in this post. Of particular note, I demonstrate that there exist forms of both imitative amplification and AI safety via market making that reach all the way up to R which is significant given that the largest complexity class that any alignment proposal was known to access previously was NEXP . Only the forms of amplification and market making making use of pointers (as in strong HCH), however, can access R for the pointer-less versions, I demonstrate in this post that they access PSPACE and EXP , respectively. The EXP proof for market making is also particularly notable as it is the only approach on my list that ends up in that complexity class. Additionally, I also demonstrate that recursive reward modeling can reach all the way to PSPACE , improving upon the previous best result in “Scalable agent alignment via reward modeling” that it accesses NP Before I jump in, however, some preliminaries. First, we'll assume that a human, H , is polynomial-time such that H can reliably solve any problem in P but not anything beyond that. Second, we'll assume that our training procedure and resulting models are arbitrarily strong in terms of what complexity class they can access. Third, we'll assume that H gets oracle access to the models during training. Then, we'll say that a proposal to train a model M using a loss function L M accesses a complexity class C iff, for any language l ∈ C , there exists some strategy available to H such that, for any M which is optimal under L M given H 's strategy, M x x ∈ l . Thus, conceptually, a proposal accesses C if there is a (polynomial-time) strategy that you (a human) can implement such that—conditional on you knowing that the model is optimal—you would trust the model's output for any problem in C . Note that that is not the same as saying that a polynomial-time human would actually be able to verify that the result is correct—only that it will always be correct at optimum. Note that these assumptions are just generalizations of those used in “AI safety via debate.” Irving et al. actually note that, if you don't imagine optimal play and simply restrict to the set of problems that a polynomial-time human can actually verify, debate only reaches NP rather than PSPACE Alignment proposals by complexity class Without further ado, here's my list of alignment proposals grouped by what complexity class they access. All of the proofs below are only lower bounds rather than upper bounds, so the proposals could be stronger than is noted here, but shouldn't be weaker. EDIT: This list is now out of date. See “Weak HCH accesses EXP ” for the updated version. P : Imitation learning (very straightforward—given H ∈ P , optimal imitation of H will also be in P PSPACE : AI safety via debate (proof), Imitative amplification with weak HCH (proof below), Approval-based amplification (proof below), Recursive reward modeling (proof below) EXP : AI safety via market making (proof below) NEXP : Debate with cross-examination (proof) R : Imitative amplification with strong HCH (proof below), AI safety via market mak...