Polylog depth, highness and lowness for E (Q2304528): Difference between revisions

The author studies the relations between the notions of highness, lowness and logical depth using time complexity. The notion of polylog depth is based on time-bounded Kolmogorov complexity; it satisfies all basic logical depth properties, namely sets in P are not polylog deep, sets with (time-bounded) Kolmogorov complexity greater than polylog are not polylog deep, and only polylog deep sets can polynomially Turing compute a polylog deep set. Furtheromore, i) if NP does not have p-measure zero, then NP contains polylog deep sets, ii) every high set for E contains a polylog deep set in its polynomial Turing degree, and iii) that there exist Low(E, EXP) polylog deep sets.