# Is it possible to infer on the thermodynamics of 2 problems if reduction from $B$ to $A$ exists?

Peter Shor commented on this post:

years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar.

1. What do we know about the distribution/thermodynamics of $A$ w.r.t to $B$ if we know that $A \le_M B$ (there is a reduction from $B$ to $A$) or where we know that $A,B \in C$ where $C$ is some complexity class ($P$, $NP$, co-$NP$, etc.). I guess it's hard/impossible/wrong to use complexity theory which takes mostly the worst case and refer about thermodynamics, has a work to study thermodynamics of problems been done before?

2. What can we say on the thermodynamics if there isn't a reduction from $A$ to $B$, or given their complexity classes?

• Why would reductions(many one, others or even NP complete problems) only be the scope of study, are any results that relate to thermodynamic behaviour of problems that concern only NP complete problems. It could be the case average case complexity problems that thermodynamics of problems may fall within the scope, Issues such as P-computability, or P-samplability may be within scope, rather than reductions. – user3483902 Feb 20 '18 at 5:37
• @user3483902 I guess anything that relates complexity to thermodynamics would be interesting to study. – 0x90 Feb 20 '18 at 5:40

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to a permutation of $\Sigma^*$, and permutations can in principle be computed with zero thermodynamic cost.