Complexity and Avoidance

In this dissertation we examine the relationships between the several hierarchies, including the complexity, $\mathrm{L}\mathrm{U}\mathrm{A}$ (Linearly Universal Avoidance), and shift complexity hierarchies, with an eye towards quantitative bounds on growth rates therein. We show that for suitable $f$ and $p$, there are $q$ and $g$ such that $\mathrm{L}\mathrm{U}\mathrm{A}(q){\le }_{\mathrm{s}}\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}(f)$ and $\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}(g){\le }_{\mathrm{s}}\mathrm{L}\mathrm{U}\mathrm{A}(p)$, as well as quantify the growth rates of $q$ and $g$. In the opposite direction, we show that for certain sub-identical $f$ satisfying ${\lim }_{n\to \mathrm{\infty }}f(n)\mathrm{/}n=1$ there is a $q$ such that $\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}(f){\le }_{\mathrm{w}}\mathrm{L}\mathrm{U}\mathrm{A}(q)$, and for certain fast-growing $p$ there is a $g$ such that $$\mathrm{L}\mathrm{U}\mathrm{A}$(p) \leq_$\mathrm{s}$ $\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}$(g)$,aswellasquantifythegrowthratesof$q$and$g$. Concerning shift complexity, explicit bounds are given on how slow-growing $q$ must be for any member of $\mathrm{L}\mathrm{U}\mathrm{A}(q)$ to compute $\delta$-shift complex sequences. Motivated by the complexity hierarchy, we generalize the notion of shift complexity to consider sequences $X$ satisfying $\operatorname{KP}(\tau) \geq f(|\tau|) - O(1)$forallsubstrings$\tau$of$X$where$f$ is any order function. We show that for sufficiently slow-growing $f$, $f$-shift complex sequences can be uniformly computed by $g$-complex sequences, where $g$ grows slightly faster than $f$. The structure of the $\mathrm{L}\mathrm{U}\mathrm{A}$ hierarchy is examined using bushy tree forcing, with the main result being that for any order function $p$, there is a slow-growing order function $q$ such that $\mathrm{L}\mathrm{U}\mathrm{A}(p)$ and $\mathrm{L}\mathrm{U}\mathrm{A}(q)$ are weakly incomparable. Using this, we prove new results about the filter of the weak degrees of deep nonempty ${\mathrm{\Pi }}_1^0$ classes and the connection between the shift complexity and $\mathrm{L}\mathrm{U}\mathrm{A}$ hierarchies.