Low-Depth Witnesses are Easy to Find

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time- bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP. We also show that assuming good pseudorandom generators one cannot increase the depth of a string efficiently.