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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Oct 2 '13 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.