21
votes
Accepted
Entropy and computational complexity
Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
- 38.5k
9
votes
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. ...
- 51.2k
6
votes
Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?
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 ...
- 38.5k
2
votes
Accepted
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
It was only recently (2016) that it was proved mathematically that all of classical spin physics can be reproduced by the 2D Ising Model with linear terms (what physicists call "fields") with at most ...
- 541
2
votes
Physics results in TCS?
I know some examples in machine learning. It is very common for thermodynamic ideas to be used in this area: Boltzmann machine, Hopfield network, Wake-sleep algorithm. Markov Chain were initially used ...
- 583
Only top scored, non community-wiki answers of a minimum length are eligible