5
$\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 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). Here is somehow a related work that states "NP problems" in terms of an Ising model.

Improve this question
$\endgroup$
4
  • $\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
    Commented Feb 20, 2018 at 5:37
  • $\begingroup$ @user3483902 I guess anything that relates complexity to thermodynamics would be interesting to study. $\endgroup$
    – 0x90
    Commented Feb 20, 2018 at 5:40
  • $\begingroup$ @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'? $\endgroup$
    – A.2
    Commented Jul 3, 2020 at 16:53
  • $\begingroup$ @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. $\endgroup$
    – 0x90
    Commented Jul 3, 2020 at 17:02

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Are you referring to efficiently computable and invertible permutations implied by the isomorphism conjecture? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jan 22, 2019 at 16:25
  • 2
    $\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
    Commented Jan 23, 2019 at 7:10
  • $\begingroup$ What do you mean by “complexity of functions”? Are these the reducing/mapping functions? $\endgroup$
    – 0x90
    Commented Jul 5, 2020 at 2:38
  • $\begingroup$ @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) $\endgroup$
    – Joshua Grochow
    Commented Jul 6, 2020 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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