Cryptographic hardness under projections for time-bounded Kolmogorov complexity

A version of time-bounded Kolmogorov complexity, denoted , has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem . Essentially all results about the complexity of hold also for (the problem of computing the complexity of a string). Both and are hard for (Statistical Zero Knowledge) under -Turing reductions; neither is known to be -complete.Recently, some hardness results for were proved that are not (yet) known to hold for . In particular, is hard for (a subclass of ) under nonuniform reductions. In this paper, we improve this, to show that is hard for the (apparently larger) class under not only reductions but even under projections. Also is hard for under reductions. Here, is the class of problems with non-interactive zero-knowledge proofs, and is the non-interactive version of the class that was studied by Dvir et al.As an application, we provide several improved worst-case to average-case reductions to problems in , and we obtain a new lower bound on (which is currently not known to hold for ).