  This paper proposes new notions of polynomial depth (called monotone poly
depth), based on a polynomial version of monotone Kolmogorov complexity. We
show that monotone poly depth satisfies all desirable properties of depth
notions i.e., both trivial and random sequences are not monotone poly deep,
monotone poly depth satisfies the slow growth law i.e., no simple process can
transform a non deep sequence into a deep one, and monotone poly deep sequences
exist (unconditionally). We give two natural examples of deep sets, by showing
that both the set of Levin-random strings and the set of Kolmogorov random
strings are monotone poly deep.
