We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.
The Kolmogorov measures that have been introduced have many advantages over other approaches to defining resource-bounded Kolmogorov complexity (such as much greater independence from the underlying choice of universal machine that is used to define the measure) [ABKMR]. Here, we study the properties of other measures that arise naturally in this framework.

The motivation for introducing yet more notions of resource-bounded Kolmogorov complexity are two-fold:
* to demonstrate that other complexity measures such as branching-program size and formula size can also be discussed in terms of Kolmogorov complexity, and
* to demonstrate that notions such as nondeterministic Kolmogorov complexity and distinguishing complexity [BFL] also fit well into this framework.

The main theorems that we provide using this new approach to resource-bounded Kolmogorov complexity are:
* A complete set ($\RKNt$) for NEXP/poly defined in terms of strings of high Kolmogorov complexity.
* A lower bound, showing that $\RKNt$ is not in NP intersect coNP.
* New conditions equivalent to the conditions ``NEXP is contained in nonuniform NC1'' and ``NEXP is contained in L/poly''.
* Theorems showing that ``distinguishing complexity'' is closely connected to both FewEXP and to EXP.
* Hardness results for the problems of approximating formula size and branching program size.