# Information theoretic characterization and consequences of reductions between computational problems

For two computational problems $A$ and $B$ in complexity class C (let say $NP$), the existence of a reduction $A <_m^L B$ computable in class (say $L$) implies that $A$ is not computationally harder than $B$ and $B$ is at least as hard as $A$.

I am interested in information theoretic characterization and implications for the existence and non-existence of $<_m^L$-reductions between computational problems. I'm aware of concepts such as computational entropy and hardness amplification but my limited understanding of these notions, which I guess originated from cryptographic applications, does not seem to shed light on the information theoretic characterization of $<_m^L$-reductions.

What is known about information theoretic characterization and consequences of the existence and non-existence of such reductions? Can notions such as computational entropy and hardness amplification help in answering my previous question?

• You might be interested in the poly-time bounded analogs of Hausdorff measure and Hausdorff dimension as in the works of Lutz, Hitchcock, Mayordomo, Moser, and others. I think it's probably a little different than what you're after, but maybe it will inspire some related ideas. – Joshua Grochow Oct 2 '13 at 19:15