<p>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 <em>permutation</em> of $\Sigma^*$, and permutations can in principle be computed with zero thermodynamic cost.</p>

CC BY-SA 4.0
2019-01-22T16:25:09.340Z
Are you referring to efficiently computable and invertible permutations implied by the isomorphism conjecture?
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-01-23T07:10:32.083Z
No, unconditional. Given a language L, it is equivalent to the permutation f which swaps 1x and 0x iff x is in L.
Joshua Grochow
CC BY-SA 4.0
2020-07-05T02:38:23.827Z
What do you mean by “complexity of functions”? Are these the reducing/mapping functions?
0x90
CC BY-SA 4.0
2020-07-06T03:21:30.913Z
@0x90 not necessarily. Just considering the complexity of computing functions instead of restricting attention to decision problems (which you can think of as functions with range {0,1}, as opposed to general functions with arbitrary range)
Joshua Grochow
CC BY-SA 3.0
2018-02-24T15:37:15.750Z
2018-02-24T15:37:15.750Z
Joshua Grochow
<p>Peter Shor commented on this <a href="https://cstheory.stackexchange.com/questions/40109/why-isnt-it-trivial-to-map-classical-computational-models-into-spin-glass-which">post</a>:</p>
<blockquote>
<p>years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar.</p>
</blockquote>
<hr />
<ol>
<li><p>What can we say about the distribution/thermodynamics of <span class="math-container">$A$</span> w.r.t. <span class="math-container">$B$</span> if we know that <span class="math-container">$A \le_M B$</span> (there is a reduction from <span class="math-container">$B$</span> to <span class="math-container">$A$</span>), or if we know that <span class="math-container">$A, B \in C$</span> where <span class="math-container">$C$</span> is some complexity class (<span class="math-container">$P$</span>, <span class="math-container">$NP$</span>, co-<span class="math-container">$NP$</span>, etc.)?</p>
</li>
<li><p>What can we say on the thermodynamics if there isn't a reduction from <span class="math-container">$A$</span> to <span class="math-container">$B$</span>, or given their complexity classes?</p>
</li>
</ol>
<hr />
<p>I am not sure if it is a wicked idea to use complexity theory whose main concern is the worst-case scenarios while discussing thermodynamics, or statistical physics, whose general aim is to characterize phase transitions and describe the average case (<a href="https://en.wikipedia.org/wiki/Principle_of_maximum_entropy" rel="nofollow noreferrer">principle of maximum entropy</a>). Here is somehow a related <a href="https://www.frontiersin.org/articles/10.3389/fphy.2014.00005/full" rel="nofollow noreferrer">work</a> that states &quot;NP problems&quot; in terms of an Ising model.</p>

CC BY-SA 3.0
2018-02-20T05:37:52.087Z
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
CC BY-SA 3.0
2018-02-20T05:40:03.630Z
@user3483902 I guess anything that relates complexity to thermodynamics would be interesting to study.
0x90
CC BY-SA 4.0
2020-07-03T16:53:13.640Z
@0x90 A slightly orthogonal comment. Do we really need to use term 'thermodynamics' when referring to the moments (as defined in the linked question) of the distribution on problem instances. I think it is confusing. Maybe just use the terms: 'distribution' or 'properties of distribution' or 'moments'?
A.2
CC BY-SA 4.0
2020-07-03T17:02:21.493Z
@A.2, this is indeed a fair statement. Sorry for the confusion. The reason for not using moments and sticking to the thermodynamics jargon was that moments don't define the probability density function (the measure) uniquely if the system has an unbounded domain.
0x90
<cc.complexity-theory><physics><statistical-physics><random-graphs>
Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?
0x90
# Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

(Asked by: username_0 on 2018-02-14)

Peter Shor commented on this [post](https://cstheory.stackexchange.com/questions/40109/why-isnt-it-trivial-to-map-classical-computational-models-into-spin-glass-which):

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

---

1. What can we say about the distribution/thermodynamics of $A$ w.r.t. $B$ if we know that $A \le\_M B$ (there is a reduction from $B$ to $A$), or if we know that $A, B \in C$ where $C$ is some complexity class ($P$, $NP$, co-$NP$, etc.)?
2. What can we say on the thermodynamics if there isn't a reduction from $A$ to $B$, or given their complexity classes?

---

I am not sure if it is a wicked idea to use complexity theory whose main concern is the worst-case scenarios while discussing thermodynamics, or statistical physics, whose general aim is to characterize phase transitions and describe the average case ([principle of maximum entropy](https://en.wikipedia.org/wiki/Principle_of_maximum_entropy)). Here is somehow a related [work](https://www.frontiersin.org/articles/10.3389/fphy.2014.00005/full) that states "NP problems" in terms of an Ising model.

**Tags:** cc.complexity-theory, physics, statistical-physics, random-graphs

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 I guess anything that relates complexity to thermodynamics would be interesting to study.  
> **username_2**: @username_0 A slightly orthogonal comment. Do we really need to use term 'thermodynamics' when referring to the moments (as defined in the linked question) of the distribution on problem instances. I think it is confusing. Maybe just use the terms: 'distribution' or 'properties of distribution' or 'moments'?  
> **username_0**: @username_2, this is indeed a fair statement. Sorry for the confusion. The reason for not using moments and sticking to the thermodynamics jargon was that moments don't define the probability density function (the measure) uniquely if the system has an unbounded domain.  

---

## 1 answers

### Answer by username_3 on 2018-02-24. Score: 6

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.

> **Comments:**
> **username_4**: Are you referring to efficiently computable and invertible permutations implied by the isomorphism conjecture?  
> **username_3**: No, unconditional. Given a language L, it is equivalent to the permutation f which swaps 1x and 0x iff x is in L.  
> **username_0**: What do you mean by “complexity of functions”? Are these the reducing/mapping functions?  
> **username_3**: @username_0 not necessarily. Just considering the complexity of computing functions instead of restricting attention to decision problems (which you can think of as functions with range {0,1}, as opposed to general functions with arbitrary range)  

---

