Bridging Computational Notions of Depth: Members of Deep Classes

Introducing the members of deep classes and proving that they are strongly deep.

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

By Lemma 3, we can conclude that X is order-deep.

One immediate consequence of Theorem 9 is the following.

The converse of this result does not hold.