 Logical Inductors contain Logical Inductors over other complexity classes post by Scott Garrabrant 1029 days ago | Jessica Taylor, Patrick LaVictoire and Tsvi Benson-Tilsen like this | discuss In the Logical Induction paper, we give a definition of logical inductors over polynomial time traders. It is clear from our definition that our use of polynomial time is rather arbitrary, and we could define e.g. an exponential time logical inductor. However, it may be less clear that actually logical inductors over one complexity class contain logical inductors over other complexity classes within them. For this post, I will define polynomial logical inductor to be the logical inductors defined in the main paper. I will define exponential logical inductor similarly, except the traders will be allowed to run in exponential time instead of polynomial time. Theorem: If $$\{\mathbb{P}_n\}$$ is a polynomial logical inductor over $$\{D_n\}$$, then the subsequence $$\{\mathbb{P}_{2^{2^n}}\}$$ is an exponential logical inductor over $$\{D_{2^{2^n}}\}$$. Proof Sketch: $$\{\mathbb{P}_{2^{2^n}}\}$$ is clearly computable. Assume by way of contradiction that $$\{\mathbb{P}_{2^{2^n}}\}$$ is not an exponential logical inductor over $$\{D_{2^{2^n}}\}$$. Then there exists some exponential time trading strategy which exploits it. This trader runs in time at most $$c\cdot 2^{n^c}$$ for some $$c$$. But then there exists another trader which runs in polynomial time, and on input $$2^{2^n}$$ implements this trader against $$\{\mathbb{P}_n\}$$, and output’s the constant 0 trading strategy otherwise. This can be done in polynomial time, since there is a polynomial of $$2^{2^n}$$ much larger than $$c\cdot 2^{n^c}$$. Note that this trader exploits $$\{\mathbb{P}_n\}$$, contradicting the assumption that $$\{\mathbb{P}_n\}$$ is a polynomial logical inductor over $$\{D_n\}$$. Clearly, this generalizes to other pairs of complexity classes as well. Observe that the converse is not necessarily true. In particular $$\{\mathbb{P}_n\}$$ may not even converge when $$\{\mathbb{P}_{2^{2^n}}\}$$ is an exponential logical inductor over $$\{D_{2^{2^n}}\}$$. However logical inductors trivially contain logical inductors over smaller complexity classes, since logical inductors are themselves logical inductors over all smaller complexity classes. Combining this insight with that of Universal Inductors, we can now define a singe universal inductor, and use it to get a logical inductor by conditioning on a theory, and also use it to get universal and logical inductors over larger complexity classes, by taking sparse subsequences.

### NEW DISCUSSION POSTS

[Note: This comment is three
 by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
 by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
 by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
 by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
 by Vanessa Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
 by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
 by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes