4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user3483902 Feb 20 '18 at 5:37
  • $\begingroup$ @user3483902 I guess anything that relates complexity to thermodynamics would be interesting to study. $\endgroup$ – 0x90 Feb 20 '18 at 5:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you referring to efficiently computable and invertible permutations implied by the isomorphism conjecture? $\endgroup$ – Mohammad Al-Turkistany Jan 22 at 16:25
  • $\begingroup$ No, unconditional. Given a language L, it is equivalent to the permutation f which swaps 1x and 0x iff x is in L. $\endgroup$ – Joshua Grochow Jan 23 at 7:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.