Weak HCH accesses EXP

post by evhub · 2020-07-22T22:36:43.925Z · LW · GW · 0 comments

Contents

  Updated list of proposals by complexity class
  Proofs
    Imitative amplification with weak HCH accesses EXP
    Approval-based amplification accesses EXP
    Recursive reward modeling accesses EXP
None
No comments

This post is a follow-up to my “Alignment proposals and complexity classes [AF · GW]” post. Thanks to Sam Eisenstat for helping with part of the proof here.

Previously [AF · GW], I proved that imitative amplification [AF · GW] with weak HCH, approval-based amplification [AF · GW], and recursive reward modeling access $\text{PSPACE}$ while AI safety via market making [AF · GW] accesses $\text{EXP}$. At the time, I wasn't sure whether my market making proof would generalize to the others, so I just published it with the $\text{PSPACE}$ proofs instead. However, I have since become convinced that the proof does generalize—and that it generalizes for all of the proposals I mentioned—such that imitative amplification with weak HCH, approval-based amplification, and recursive reward modeling all actually access $\text{EXP}$. This post attempts to prove that.

Updated list of proposals by complexity class

$\text{P}$: Imitation learning (trivial)

$\text{PSPACE}$: AI safety via debate (proof)

$\text{EXP}$: AI safety via market making [AF · GW] (proof [AF · GW]), Imitative amplification with weak HCH (proof below), Approval-based amplification [AF · GW] (proof below), Recursive reward modeling (proof below)

$\text{NEXP}$: Debate with cross-examination [AF · GW] (proof)

$\text{R}$: Imitative amplification with strong HCH (proof [AF · GW]), AI safety via market making with pointers (proof [AF · GW])

Proofs

Imitative amplification with weak HCH accesses $\text{EXP}$

The proof here is similar in structure to my previous proof that weak HCH accesses $\text{PSPACE}$ [AF · GW], so I'll only explain where this proof differs from that one.

First, since $l\in \text{EXP}$, we know that for any $x\in X$, $T_l\left(x\right)$ halts in $O\left(2^{\text{poly}\left(n\right)}\right)$ steps where $n=|x|$. Thus, we can construct a function $f_l\left(n\right)=c_1+c_2{e}^{c_3{n}^{c_4}}$ such that for all $x\in X$, $T_l\left(x\right)$ halts in less than or equal to $f_l\left(x\right)$ steps by picking $c_3,c_4$ large enough that they dominate all other terms in the polynomial for all $n\in N$. Note that $f_l$ is then computable in time polynomial in $n$.

Second, let $H$'s new strategy be as follows:

1. Given $p$, let $s,x=M(p:f(|x|\left)\right)$. Then, return accept/reject based on whether $s$ is an accept or reject state (it will always be one or the other)
2. Given $p:0$, return $s_0,x_0$ where $s_0$ is the starting state and $x_0$ is the empty tape symbol.
3. Given $p:i$, let $$\begin{array}{cc}& s,x=M(p:i-1)\\ & x_{\text{left}}=M(p:i-1:-1)\\ & x_{\text{right}}=M(p:i-1:1).\end{array}$$ Then, return $s^{\prime },x^{\prime }$ where $s^{\prime }$ is the next state of $T_l$ from state $s$ over symbol $x$ (where if we're already in an accept/reject state we just stay there) and $x^{\prime }$ is the new tape symbol at the head (which can be determined given $s,x,x_{\text{left}},x_{\text{right}}$).
4. Given $p:0:j$, return $x_0$.
5. Given $p:i:j$, let $s,x_{\text{head}}=M(p:i-1)$. Then, let $h$ be the amount by which $T_l$ on $s,x_{\text{head}}$ changes the head position by (such that $h\in \{-1,0,1\}$). If $j+h=0$, let $s^{\prime },x^{\prime }=M(p:i-1)$ otherwise let $x^{\prime }=M(p:i-1:j+h)$. Return $x^{\prime }$.

Note that this strategy precisely replicates the strategy used in my proof that market making accesses $\text{EXP}$ [AF · GW] for inputs $p:i$ and $p:i:j$. Thus, I'll just defer to that proof for why the strategy works and is polynomial time on those inputs. Note that this is where $l\in \text{EXP}$ becomes essential, as it guarantees that $i$ and $j$ can be represented in polynomial space.

Then, the only difference between this strategy and the market making one is for the base $p$ input. On $p$, given that $M(p:i)$ works, $M(p:f(|x|\left)\right)$ will always return a state after $T_l$ has halted, which will always be an accept state if $T_l$ accepts and a reject state if it rejects. Furthermore, since $|M(p:f(|x|)|\in O(1)$ and $f$ is computable in polynomial time, the strategy for $p$ is polynomial, as desired.

Since this procedure works for all $l\in \text{EXP}$, we get that amplification with weak HCH accesses $\text{EXP}$, as desired.

Approval-based amplification accesses $\text{EXP}$

The proof here is almost precisely the same as my previous proof that approval-based amplification accesses $\text{PSPACE}$ [AF · GW] with the only modification being that we need to verify that $|M\left(q\right)|+|H(q,M)|$ are still polynomial in size for the new imitative amplification strategy given above. However, the fact that $i$ and $j$ are bounded above by $t_p$ [AF · GW] means that they are representable in polynomial space, as desired.

Recursive reward modeling accesses $\text{EXP}$

Again, the proof here is almost precisely the same as my previous proof that recursive reward modeling accesses $\text{PSPACE}$ [AF · GW] with the only modification being the same as with the above proof that approval-based amplification accesses $\text{EXP}$.

0 comments

Comments sorted by top scores.