We show that all sets complete for NC$^1$ under AC$^0$ reductions are isomorphic under AC$^0$-computable isomorphisms. Although our proof does not generalize directly to other complexity classes, we do show that, for all complexity classes C closed under NC$^1$-computable many-one reductions, the sets complete for C under NC$^0$ reductions are ... more >>>

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range is the set of tautologies in Propositional Logic (TAUT), is called a proof system. Cook and Reckhow defined this concept and in order to compare the relative strenth of different proof systems, they considered the notion of p-simulation. Intuitively a proof system ... more >>>

We consider sets of strings with high Kolmogorov complexity, mainly in resource-bounded settings but also in the traditional recursion-theoretic sense. We present efficient reductions, showing that these sets are hard and complete for various complexity classes. In particular, in addition to the usual Kolmogorov complexity measure K, we consider the ... more >>>