Table of Links
Abstract and 1 Introduction
2 Background
3 On the slow growth law
4 Members of Deep Π0 1 classes
5 Strong depth is Negligible
6 Variants of Strong Depth
References
Appendix A. Proof of Lemma 3
2. Background
Lemma 1 ([BDM23]).
In addition, we need the following theorem (see, e.g. [JLL94, Theorem 4.3(2)]).
Note that by combining Lemma 1(iii) and Theorem 2, we obtain a resource-bounded analogue of Levin’s coding theorem.
In the rest of the paper we will sometimes use an equivalent characterization of order-depth, given by the following lemma.
The proof of this lemma is technical; for the sake of readability, we defer it to the appendix.
The slow growth law also holds for order-depth.
:::info
This paper is available on arxiv under CC BY 4.0 DEED license.
:::
:::info
Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter.
:::
