Abstract:
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 how to find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumptions though fails if BPP = UP = EXP. We also show that under standard hardness assumptions one cannot increase the depth of a string efficiently and that such an assumption is required.