<p>Complex systems is a field has a lot to do with social network analysis, and networks in general, and has been invaded by physicists in large numbers, wielding weapons from statistics and thermodynamics. Whether it's been invaded by physics is a different story.</p>

CC BY-SA 3.0
2011-06-13T17:03:15.300Z
I'm developing quite a strong interest in networks and social network analysis. Do you have any references?
Dave Clarke
CC BY-SA 3.0
2011-06-14T09:33:46.063Z
hmm. Best to start with the Kleinberg/Easley book (which is a good undergrad-level text). Then you could work forwards and backwards from work by Aaron Clauset and Mark Newman
Suresh Venkat
CC BY-SA 2.5
2010-10-10T17:35:49.160Z
2010-10-10T17:35:49.160Z
Suresh Venkat
<p>A result of Pour-El and Richards <a href="http://dx.doi.org/10.1016/0001-8708%2881%2990001-3"><em>Adv. Math.</em> <strong>39</strong> 215 (1981)</a> gives the existence of noncomputable solutions to the 3D wave equation for computable initial conditions by using the wave to simulate a universal Turing machine. </p>

CC BY-SA 2.5
2010-10-10T02:08:08.823Z
I would also mention DNA computing as an area of overlap, albeit with more tenuous connections to theoretical physics per se.
S Huntsman
CC BY-SA 2.5
2010-10-10T12:49:05.573Z
I more had in mind areas where TCS benefited from results in physics, rather than the other way around.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T17:34:24.860Z
Well then (although it might be considered implicit in or related to some other stuff mentioned on this page) I would be remiss in not mentioning the theory of reversible computation, most notably the circle of ideas born from Landauer's work, which has influenced many more areas besides quantum computing.
S Huntsman
CC BY-SA 2.5
2010-10-10T17:45:38.650Z
To comment on Suresh's answer (not enough rep to comment there): there have been many fruitful applications of ideas in physics to the analysis of *dynamics* on networks. As one example I recall a paper discussing evidence that TCP traffic exhibited self-organized criticality. As another example a few researchers (including myself) have worked on applying ideas from physics (not just entropy) to characterizing network traffic for anomaly detection. Of course, this leaves the T out of TCS.
S Huntsman
CC BY-SA 2.5
2010-10-10T02:01:01.463Z
2010-10-10T02:01:01.463Z
S Huntsman
<p>The connection goes the other way around, too. A while ago theoretical computer scientists who work in domain theory got interested in relativity. They proved results about how to reconstruct the structure of spacetime from the causality structure. This is something quite familiar to domain theorists, where the beasic objects of interest are partial orders whose topology is determined by the order. You might have a look at  <a href="http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf">http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf</a></p>

CC BY-SA 2.5
2010-10-11T12:05:50.837Z
Yes, actually I heard Prakash speak about this at his workshop in Barbados. Really interesting work. I was however under the impression that he also had a physics background. That aside, there are certainly contributions in both directions. It just happens that I was particularly interested in finding out about one direction in particular. Presumably asking about the influence of TCS on physics would be better suited to a physics website, since people in the field which adapts ideas from a second field are better placed to determine which of these have made significant impact on the first.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-11T11:29:05.437Z
2010-10-11T11:29:05.437Z
Andrej Bauer
<p>The search technique <a href="http://en.wikipedia.org/wiki/Simulated_annealing">simulated annealing</a> is inspired by the physical process of <a href="http://en.wikipedia.org/wiki/Annealing_%28metallurgy%29">annealing</a> in metallurgy. </p>

<p>Annealing is a heat treatment where the strength and hardness of the substance being treated can change dramatically. Often this involves heating the substance to an extreme temperature and then allowing it to cool slowly.</p>

<p>Simulated annealing avoids local minima/maxima in search spaces by incorporating a degree of randomness (the temperature) in the search process. As the search process proceeds, the temperature gradually cools, which means that the amount of randomness in the search decreases. Apparently it is quite an effective search technique.</p>

CC BY-SA 3.0
2011-07-15T21:25:52.690Z
Of course, it bears noting that 'real' annealing doesn't always avoid local minima either! Defects (in the mathematical-physics sense) aren't unheard of.
Steven Stadnicki
CC BY-SA 3.0
2012-02-19T23:19:30.797Z
If the temperature decrease takes places exponentially slowly, then simulated annealing gains many desirable global optimization properties. Of course, it also gains an exponential run time.
Elliot JJ
CC BY-SA 2.5
2010-10-11T14:00:47.103Z
supercooldave: My limited understanding was that simulated annealing only avoids local minima that are "sufficiently shallow."  Is that correct?
Joshua Grochow
CC BY-SA 2.5
2010-10-11T14:04:33.753Z
@Joshua: in general, simulated annealing does not always manage to avoid local minimal. It can always get stuck in the wrong place. Some experimentation is required to find a good starting point and so forth.
Dave Clarke
CC BY-SA 2.5
2010-10-10T14:52:39.363Z
2010-10-10T15:15:47.010Z
2010-10-10T15:15:47.010Z
Dave Clarke
<p>Going the other way around (from TCS to physics), matrix product states, PEPS (projected entangled pair states), MERA (multiscale entanglement renomalization ansatz) have been significantly informed by TCS ideas which were adapted in quantum information theory. These acronyms are all techniques for approximating the states of quantum spin systems that are used by condensed matter theorists, and in many cases these techniques seem to work better than any tools previously known.</p>

CC BY-SA 3.0
2011-07-15T21:24:09.057Z
(@Shor) I liked this answer very much, and have provided a companion answer with several more references---at least one of which (Joseph Landsburg's 2008 survey *Geometry and the complexity of matrix multiplication*) is most definitely at the TCS end of the spectrum. http://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs/7401#7401
John Sidles
CC BY-SA 2.5
2010-10-23T22:22:53.677Z
One thing that has struck me about this area is that it seems to be more the theoretical physics community within quantum information rather than the TCS community (if we can really make such a distinction) that seems to be interested in these techniques.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-23T23:59:30.733Z
I would definitely agree. I tried to get a grad student interested in them early on, but his reaction was "bleah ... these are just heuristic approximation methods, and you can't say anything rigorous about them." Of course, this turned out to be incorrect.
Peter Shor 
CC BY-SA 3.0
2010-10-23T03:54:09.537Z
2011-05-25T07:38:46.267Z
2011-05-25T07:38:46.267Z
Peter Shor 
<p>A very old example (which could be subsumed by Suresh's answer, however, this is a different tack) is the influence of the theory of electrical networks, e.g. Kirchhoff's circuit laws, on combinatorics, graph theory, and probability.</p>

CC BY-SA 2.5
2010-10-11T11:19:26.847Z
2010-10-11T11:19:26.847Z
RJK
<p>Gauge Theory for heuristic approximations to integer programming (a few of <a href="http://cnls.lanl.gov/~chertkov/">Misha Chertkov's</a> papers). Renormalization group methods for combinatoric counting, Ch.10-12 of Rudnick/Gaspari's "Elements of the Random Walk." Applying Feymann's path integral decomposition (ie, Section 9.5.1) to counting self-avoiding walks. For connection to TCS, note that regime of tractability for approximate counting on graphs depends on the growth rate of self-avoiding walks.</p>

CC BY-SA 2.5
2010-10-23T05:08:05.183Z
2010-10-23T05:26:01.147Z
2010-10-23T05:26:01.147Z
Yaroslav Bulatov
<p>One area that has seen a few applications, but not IMO enough is approximating discrete structures or processes with analytic approximations. This is big business in mathematics (eg., analytic number theory) and physics (all of statistical mechanics), but hasn't proved as popular in CS for some reason. </p>

<p>A famous application of this was in the design of the Connection Machine. This was a massively parallel machine, and as part of its design they need to figure out how big to make the buffers in the router. Feynman modelled the router with PDEs, and showed the buffers could be smaller than the traditional inductive arguments could establish. Danny Hillis recounts the story <a href="http://www.longnow.org/essays/richard-feynman-connection-machine/">in this essay</a>. </p>

CC BY-SA 2.5
2010-10-11T13:08:23.587Z
What about analytic combinatorics (Flajolet and Sedgewick)?
RJK
CC BY-SA 2.5
2010-10-11T12:12:29.147Z
2010-10-11T12:12:29.147Z
Neel Krishnaswami
<p><a href="http://en.wikipedia.org/wiki/Force-based_algorithms_%28graph_drawing%29">Force-based graph drawing algorithms</a> are another example. The idea is to consider each edge to be a spring and the layout of the nodes of the graph corresponds to finding equilibrium in the collection of springs.</p>

CC BY-SA 3.0
2011-05-25T14:13:43.437Z
I wouldn't have thought that particularly TCS, but it's such a cool technique you get a +1 from me. After all, some areas of computer science are very heavily dependent on physics (i.e. SIGGRAPH).
Joe Fitzsimons
CC BY-SA 3.0
2011-05-25T14:17:58.113Z
Graphs are surely TCS. And they need to be drawn. And David Eppstein does graph drawing. (This is my compelling argument.)
Dave Clarke
CC BY-SA 3.0
2011-05-25T14:21:34.867Z
Ok, I'll accept that argument.
Joe Fitzsimons
CC BY-SA 3.0
2011-05-25T14:34:57.003Z
This technique is a major player in graph drawing. definitely worth mentioning
Suresh Venkat
CC BY-SA 3.0
2011-07-22T21:29:14.643Z
Great example! +1 from me
George
CC BY-SA 3.0
2011-05-25T08:38:47.007Z
2011-05-25T08:38:47.007Z
Dave Clarke
<p>I have fleshed-out this answer with <a href="https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write/70941#70941">an extended answer</a> on <i>MathOverflow</i> to Gil Kalai's community wiki question "[What is] <a href="https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write">A Book You Would Like to Write</a>."  </p>

<p>The extended answer seeks to link fundamental issues in TCS and QIT to practical issues in healing and regenerative medicine. 
<hr>
This answer extends <a href="https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs/2407#2407">Peter Shor's answer</a>, which discusses the roles of matrix product states in TCS and physics.  Two recent surveys in the <em>Bulletin of the AMS</em> are relevant to matrix product states, and both surveys are well-written, free of pay-wall restrictions, and reasonably accessible to non-specialists:</p>

<ul>
<li><p>Joseph M. Landsberg's <em><a href="http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/home.html" rel="nofollow noreferrer">Geometry and the complexity of matrix multiplication</a></em> (2008)</p></li>
<li><p>Alvaro Pelayo's and San Vu Ngoc's <em><a href="http://www.ams.org/journals/bull/2011-48-03/S0273-0979-2011-01338-6/home.html" rel="nofollow noreferrer">Symplectic theory of completely integrable Hamiltonian systems</a></em></p></li>
</ul>

<p>The mathematical arena for Landsberg's survey is <a href="http://books.google.com/books?id=_XxZdhbtf1sC&amp;pg=PA89" rel="nofollow noreferrer">secant varieties of Segre varieties</a>, while the arena for Pelayo's and Ngoc's survey is four-dimensional symplectic manifolds&nbsp;&hellip; it takes awhile to appreciate that these two arenas both are matrix product states, as viewed respectively from a computational perspective (Landsburg) and a geometric perspective (Palayo and Ngoc).  Moreover, Palayo and Ngoc include in their survey a discussion of Babelon, Cantini, and Douçot's <em><a href="http://iopscience.iop.org/1742-5468/2009/07/P07011/" rel="nofollow noreferrer">A semi-classical study of the Jaynes–Cummings model</a></em> (noting that the Jaynes–Cummings model is often encountered in the literature of condensed matter physics and quantum computing).</p>

<p>Each of these references goes far to illuminate the others.  In particular, it has been helpful in our own (very practical) spin dynamical calculations to appreciate that the quantum state-spaces that are described variously in the literature as tensor network states, matrix product states, and secant varieties of Segre varieties are richly endowed with singularities whose algebraic, symplectic, and Riemannian structure is at present very incompletely understood (as Pelayo and Ngoc review).  </p>

<p>For our engineering purposes, the <a href="http://faculty.washington.edu/sidles/ENC_2011/index.html#burningArrow" rel="nofollow noreferrer">Landsburg/algebraic geometry approach</a>, in which the state-space of quantum dynamics is viewed as an algebraic variety rather than a vector space, is emerging as the most mathematically natural.  This is surprising to us, but in common with many researchers, we find that the toolset of algebraic geometric is gratifyingly effective in validating and speeding practical quantum simulations.</p>

<p>Quantum simulationists presently enjoy the puzzling circumstance that large numerical quantum simulations very often perform much better than we have any known reason to expect.   As mathematicians and physicists arrive at a shared understanding, this puzzlement surely will diminish and the enjoyment surely will remain.  Good! :) </p>

CC BY-SA 3.0
2011-07-15T21:21:52.753Z
2011-07-22T18:55:19.510Z
2017-04-13T12:57:54.777Z
John Sidles
<p>Early distributed systems theory, especially papers by Leslie Lamport et al., has had some impact from Special Relativity to get the correct picture w.r.t. to (fault-tolerant) agreement on a global system state. See entry 27. (<em>Time, Clocks and the Ordering of Events in a Distributed System</em>, Communications of the ACM 21, 7   (July 1978), 558-565) in the <a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html" rel="nofollow">Writings of Leslie Lamport</a>, where Lamport gives the following background information on his paper:</p>

<blockquote>
  <p>The origin of this paper was a note
  titled The Maintenance of Duplicate
  Databases by Paul Johnson and Bob
  Thomas.  I believe their note
  introduced the idea of using message
  timestamps in a distributed algorithm.
  I happen to have a solid, visceral
  understanding of special relativity
  (see [5]).  This enabled me to grasp
  immediately the essence of what they
  were trying to do.  Special relativity
  teaches us that there is no invariant
  total ordering of events in
  space-time; different observers can
  disagree about which of two events
  happened first.  There is only a
  partial order in which an event e1
  precedes an event e2 iff e1 can
  causally affect e2.  I realized that
  the essence of Johnson and Thomas's
  algorithm was the use of timestamps to
  provide a total ordering of events
  that was consistent with the causal
  order.  This realization may have been
  brilliant.  Having realized it,
  everything else was trivial.  Because
  Thomas and Johnson didn't understand
  exactly what they were doing, they
  didn't get the algorithm quite right;
  their algorithm permitted anomalous
  behavior that essentially violated
  causality.  I quickly wrote a short
  note pointing this out and correcting
  the algorithm.</p>
</blockquote>

CC BY-SA 3.0
2010-12-03T10:04:50.380Z
2011-05-25T07:26:54.560Z
2011-05-25T07:26:54.560Z
Martin Schwarz
<p>Statistical physics has given computer scientists a novel way of looking at SAT, as overviewed <a href="http://www.cs.cornell.edu/gomes/gomes-selman-science.pdf">here</a>. The idea is that as the ratio of clauses to variables involved in a 3-SAT formula increases from around 4 to around 5 we go from being able to solve the vast majority of 3-SAT instances to being able to solve very few. This transition is regarded as a "phase change" in SAT.</p>

<p>This idea gained particular notoriety this past summer from Deolalikar's alleged P vs. NP paper.</p>

CC BY-SA 2.5
2010-12-03T07:46:00.730Z
Yikes, I just realized that Joe referenced this in his original question. Hopefully this elaborates a bit.
Huck Bennett
CC BY-SA 2.5
2010-12-03T07:40:37.673Z
2010-12-03T07:40:37.673Z
Huck Bennett
<p>Much of the math that we use was originally invented to solve physics problems. Examples include calculus (Newtonian gravity) and Fourier series (heat equation).</p>

CC BY-SA 2.5
2010-10-10T17:33:40.123Z
In a similar vein, Belkin, Narayanan and Niyogi (FOCS '06, http://dx.doi.org/10.1109/FOCS.2006.34) used mathematical analysis from the study of heat flow and diffusion to give a fast randomized algorithm for computing the surface area of a convex body in n dimensions.
arnab
CC BY-SA 2.5
2010-10-10T17:35:18.027Z
good example. although is this an example of physics or mathematics ? :)
Suresh Venkat
CC BY-SA 2.5
2010-10-10T14:20:40.077Z
2010-10-10T14:20:40.077Z
Warren Schudy
<p>I know some examples in machine learning. It is very common for thermodynamic ideas to be used in this area: <a href="https://en.wikipedia.org/wiki/Boltzmann_machine" rel="nofollow noreferrer">Boltzmann machine</a>, <a href="https://en.wikipedia.org/wiki/Hopfield_network" rel="nofollow noreferrer">Hopfield network</a>, <a href="https://en.wikipedia.org/wiki/Wake-sleep_algorithm" rel="nofollow noreferrer">Wake-sleep algorithm</a>. <a href="https://en.wikipedia.org/wiki/Markov_chain" rel="nofollow noreferrer">Markov Chain</a> were initially used in physics, and today they have applications in reinforcement learning. And has a technique (<a href="https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Momentum" rel="nofollow noreferrer">Momentum</a>) that is used to improve the optimization algorithm of gradient descedent, which is inspired by a concept that comes from mechanics.</p>
<p>The mathematical technique used in <a href="https://en.wikipedia.org/wiki/Lagrangian_mechanics" rel="nofollow noreferrer">Lagrangian Mechanics</a> are also used in <a href="https://en.wikipedia.org/wiki/Lagrange_multiplier" rel="nofollow noreferrer">optimization</a>. As already stated, many ideas in mathematics were initially developed to solve physics problems.</p>

CC BY-SA 4.0
2021-01-08T19:03:35.383Z
2021-01-08T19:03:35.383Z
Raphael Augusto
<p>There is a recent paper which establishes the connection between Computer Security and the 2nd principal of thermodynamic.<br>
<a href="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166" rel="nofollow">http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166</a></p>

CC BY-SA 3.0
2014-04-25T22:17:51.170Z
2014-04-25T22:17:51.170Z
sean
<p>The concept of potential is related to many different areas of physics. In cs, potential is used in amortized analysis of data structures. We can look at how each step affects the entropy of the system and  therefore get an average (amortized) cost of an operation with a given data structure. This has given rise to many theoretically better data structures like the fibonacci heap.</p>

CC BY-SA 3.0
2013-01-21T21:23:16.453Z
2013-01-21T21:23:16.453Z
Nate
<p>to add/fill in some gap in the current excellent answers/coverage—there seems to be a strong connection between TCS and thermodynamics in various ways that hasnt yet been fully explored but is the frontiers of active research. there is a transition point associated with SAT but it seems possibly there are transition points associated with other (or even all) complexity classes as well. the SAT transition point is associated with a difference between "easy" (P) and "hard" (NP) instances, but arguably all complexity class boundaries must lead to the same transition point-like property.</p>

<p>consider a Turing Machine. it already measures its operation in normally <em>physical</em> dimensions of "time" and "space". but note that it apparently also does one unit of "work" in moving from square to square and making a transition. in physics the unit of work is Joules, which is also a measure of energy. so it appears that complexity classes have some relation to energy levels, boundaries, or regimes.</p>

<p>quantum mechanics theory increasingly sees space and time itself, the universe, as a sort of computing system. it appears it has some "minimal computation units" intrinsic to its nature, probably related to the Plank length. so examination of minimal Turing machines for problems also implies and relates to minimal physical/energy systems or even volumes of space required. [3]</p>

<p>also, the key concept of <strong>entropy</strong> shows up repeatedly in TCS and physics/thermodynamics and may be a unifying principle with still more active research revealing its underlying nature. [1,2]</p>

<p>[1] <a href="http://en.wikipedia.org/wiki/Entropy_(information_theory)" rel="nofollow noreferrer">entropy in information theory</a>, wikipedia</p>

<p>[2] <a href="https://stackoverflow.com/questions/510412/what-is-the-computer-science-definition-of-entropy">what is the CS defn of entropy</a>, stackoverflow</p>

<p>[3] <a href="https://cstheory.stackexchange.com/questions/1593/what-is-the-volume-of-information">What is the Volume of Information?</a> tcs.se</p>

CC BY-SA 3.0
2013-01-23T15:03:23.643Z
You realise that I answered the tcs.se question, right?
Joe Fitzsimons
CC BY-SA 3.0
2014-04-27T11:50:36.513Z
I would like to understand why this question was downvoted. Downvoting without explanation helps no one, since the reasons can well be non technical. I understand that the OP was aware of some or all of this answer, but since he did not mention it in the question ...   cc @JoeFitzsimons
babou
CC BY-SA 3.0
2013-01-23T04:29:57.863Z
2013-01-23T04:29:57.863Z
2017-05-23T12:40:09.333Z
vzn
<p>It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are</p>

<ol>
<li>Quantum computation</li>
<li>Statistical mechanics results used in complexity analysis/heuristic algorithms.</li>
</ol>

<p>So my question is are there any major areas I am missing?</p>

<p>My motivation is very simple: I'm a theoretical physicist who has come to TCS via quantum information and I am curious as to other areas where the two areas overlap.</p>

<p>This is a relatively soft question, but I don't mean this to be a big-list type question. I'm looking for areas where the overlap is significant.</p>

CC BY-SA 3.0
2014-04-27T15:33:32.853Z
see also [how are physics/CS getting united](http://physics.stackexchange.com/questions/89630/how-are-physics-and-computer-science-getting-united) physics.se
vzn
CC BY-SA 2.5
2010-10-10T02:50:43.073Z
I don't know if complex systems count, so I'm not yet posting as an answer. it's a field has a lot to do with social network analysis, and networks in general, and has been invaded by physicists in large numbers, wielding weapons from statistics and thermodynamics. Whether it's been invaded by physics is a different story.
Suresh Venkat
CC BY-SA 2.5
2010-10-10T13:56:07.037Z
I would think it counts.
Joe Fitzsimons
<soft-question><quantum-computing><statistical-physics><physics>
Physics results in TCS?
Joe Fitzsimons
# Physics results in TCS?

(Asked by: username_0 on 2010-10-10)

It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are

1. Quantum computation
2. Statistical mechanics results used in complexity analysis/heuristic algorithms.

So my question is are there any major areas I am missing?

My motivation is very simple: I'm a theoretical physicist who has come to TCS via quantum information and I am curious as to other areas where the two areas overlap.

This is a relatively soft question, but I don't mean this to be a big-list type question. I'm looking for areas where the overlap is significant.

**Tags:** soft-question, quantum-computing, statistical-physics, physics

> **Comments:**
> **username_2**: I don't know if complex systems count, so I'm not yet posting as an answer. it's a field has a lot to do with social network analysis, and networks in general, and has been invaded by physicists in large numbers, wielding weapons from statistics and thermodynamics. Whether it's been invaded by physics is a different story.  
> **username_0**: I would think it counts.  
> **username_1**: see also [how are physics/CS getting united](http://physics.stackexchange.com/questions/89630/how-are-physics-and-computer-science-getting-united) physics.se  

---

## 17 answers

### Answer by username_3 on 2010-10-10. Score: 27

The search technique [simulated annealing](http://en.wikipedia.org/wiki/Simulated_annealing) is inspired by the physical process of [annealing](http://en.wikipedia.org/wiki/Annealing_%28metallurgy%29) in metallurgy.

Annealing is a heat treatment where the strength and hardness of the substance being treated can change dramatically. Often this involves heating the substance to an extreme temperature and then allowing it to cool slowly.

Simulated annealing avoids local minima/maxima in search spaces by incorporating a degree of randomness (the temperature) in the search process. As the search process proceeds, the temperature gradually cools, which means that the amount of randomness in the search decreases. Apparently it is quite an effective search technique.

> **Comments:**
> **username_8**: supercooldave: My limited understanding was that simulated annealing only avoids local minima that are "sufficiently shallow."  Is that correct?  
> **username_3**: @Joshua: in general, simulated annealing does not always manage to avoid local minimal. It can always get stuck in the wrong place. Some experimentation is required to find a good starting point and so forth.  
> **username_6**: Of course, it bears noting that 'real' annealing doesn't always avoid local minima either! Defects (in the mathematical-physics sense) aren't unheard of.  
> **username_7**: If the temperature decrease takes places exponentially slowly, then simulated annealing gains many desirable global optimization properties. Of course, it also gains an exponential run time.  

---

### Answer by username_9 on 2010-10-23. Score: 24

Going the other way around (from TCS to physics), matrix product states, PEPS (projected entangled pair states), MERA (multiscale entanglement renomalization ansatz) have been significantly informed by TCS ideas which were adapted in quantum information theory. These acronyms are all techniques for approximating the states of quantum spin systems that are used by condensed matter theorists, and in many cases these techniques seem to work better than any tools previously known.

> **Comments:**
> **username_0**: One thing that has struck me about this area is that it seems to be more the theoretical physics community within quantum information rather than the TCS community (if we can really make such a distinction) that seems to be interested in these techniques.  
> **username_9**: I would definitely agree. I tried to get a grad student interested in them early on, but his reaction was "bleah ... these are just heuristic approximation methods, and you can't say anything rigorous about them." Of course, this turned out to be incorrect.  
> **username_10**: (@Shor) I liked this answer very much, and have provided a companion answer with several more references---at least one of which (Joseph Landsburg's 2008 survey *Geometry and the complexity of matrix multiplication*) is most definitely at the TCS end of the spectrum. http://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs/7401#7401  

---

### Answer by username_2 on 2010-10-10. Score: 20

Complex systems is a field has a lot to do with social network analysis, and networks in general, and has been invaded by physicists in large numbers, wielding weapons from statistics and thermodynamics. Whether it's been invaded by physics is a different story.

> **Comments:**
> **username_3**: I'm developing quite a strong interest in networks and social network analysis. Do you have any references?  
> **username_2**: hmm. Best to start with the Kleinberg/Easley book (which is a good undergrad-level text). Then you could work forwards and backwards from work by Aaron Clauset and Mark Newman  

---

### Answer by username_4 on 2010-10-10. Score: 19

A result of Pour-El and Richards [*Adv. Math.* **39** 215 (1981)](http://dx.doi.org/10.1016/0001-8708%2881%2990001-3) gives the existence of noncomputable solutions to the 3D wave equation for computable initial conditions by using the wave to simulate a universal Turing machine.

> **Comments:**
> **username_4**: I would also mention DNA computing as an area of overlap, albeit with more tenuous connections to theoretical physics per se.  
> **username_0**: I more had in mind areas where TCS benefited from results in physics, rather than the other way around.  
> **username_4**: Well then (although it might be considered implicit in or related to some other stuff mentioned on this page) I would be remiss in not mentioning the theory of reversible computation, most notably the circle of ideas born from Landauer's work, which has influenced many more areas besides quantum computing.  
> **username_4**: To comment on Suresh's answer (not enough rep to comment there): there have been many fruitful applications of ideas in physics to the analysis of *dynamics* on networks. As one example I recall a paper discussing evidence that TCP traffic exhibited self-organized criticality. As another example a few researchers (including myself) have worked on applying ideas from physics (not just entropy) to characterizing network traffic for anomaly detection. Of course, this leaves the T out of TCS.  

---

### Answer by username_5 on 2010-10-11. Score: 17

The connection goes the other way around, too. A while ago theoretical computer scientists who work in domain theory got interested in relativity. They proved results about how to reconstruct the structure of spacetime from the causality structure. This is something quite familiar to domain theorists, where the beasic objects of interest are partial orders whose topology is determined by the order. You might have a look at <http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf>

> **Comments:**
> **username_0**: Yes, actually I heard Prakash speak about this at his workshop in Barbados. Really interesting work. I was however under the impression that he also had a physics background. That aside, there are certainly contributions in both directions. It just happens that I was particularly interested in finding out about one direction in particular. Presumably asking about the influence of TCS on physics would be better suited to a physics website, since people in the field which adapts ideas from a second field are better placed to determine which of these have made significant impact on the first.  

---

### Answer by username_11 on 2010-10-11. Score: 14

A very old example (which could be subsumed by Suresh's answer, however, this is a different tack) is the influence of the theory of electrical networks, e.g. Kirchhoff's circuit laws, on combinatorics, graph theory, and probability.


---

### Answer by username_12 on 2010-10-23. Score: 11

Gauge Theory for heuristic approximations to integer programming (a few of [Misha Chertkov's](http://cnls.lanl.gov/~chertkov/) papers). Renormalization group methods for combinatoric counting, Ch.10-12 of Rudnick/Gaspari's "Elements of the Random Walk." Applying Feymann's path integral decomposition (ie, Section 9.5.1) to counting self-avoiding walks. For connection to TCS, note that regime of tractability for approximate counting on graphs depends on the growth rate of self-avoiding walks.


---

### Answer by username_13 on 2010-10-11. Score: 11

One area that has seen a few applications, but not IMO enough is approximating discrete structures or processes with analytic approximations. This is big business in mathematics (eg., analytic number theory) and physics (all of statistical mechanics), but hasn't proved as popular in CS for some reason.

A famous application of this was in the design of the Connection Machine. This was a massively parallel machine, and as part of its design they need to figure out how big to make the buffers in the router. Feynman modelled the router with PDEs, and showed the buffers could be smaller than the traditional inductive arguments could establish. Danny Hillis recounts the story [in this essay](http://www.longnow.org/essays/richard-feynman-connection-machine/).

> **Comments:**
> **username_11**: What about analytic combinatorics (Flajolet and Sedgewick)?  

---

### Answer by username_3 on 2011-05-25. Score: 10

[Force-based graph drawing algorithms](http://en.wikipedia.org/wiki/Force-based_algorithms_%28graph_drawing%29) are another example. The idea is to consider each edge to be a spring and the layout of the nodes of the graph corresponds to finding equilibrium in the collection of springs.

> **Comments:**
> **username_0**: I wouldn't have thought that particularly TCS, but it's such a cool technique you get a +1 from me. After all, some areas of computer science are very heavily dependent on physics (i.e. SIGGRAPH).  
> **username_3**: Graphs are surely TCS. And they need to be drawn. And David Eppstein does graph drawing. (This is my compelling argument.)  
> **username_0**: Ok, I'll accept that argument.  
> **username_2**: This technique is a major player in graph drawing. definitely worth mentioning  
> **username_14**: Great example! +1 from me  

---

### Answer by username_16 on 2010-12-03. Score: 10

Statistical physics has given computer scientists a novel way of looking at SAT, as overviewed [here](http://www.cs.cornell.edu/gomes/gomes-selman-science.pdf). The idea is that as the ratio of clauses to variables involved in a 3-SAT formula increases from around 4 to around 5 we go from being able to solve the vast majority of 3-SAT instances to being able to solve very few. This transition is regarded as a "phase change" in SAT.

This idea gained particular notoriety this past summer from Deolalikar's alleged P vs. NP paper.

> **Comments:**
> **username_16**: Yikes, I just realized that Joe referenced this in his original question. Hopefully this elaborates a bit.  

---

### Answer by username_10 on 2011-07-15. Score: 9

I have fleshed-out this answer with [an extended answer](https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write/70941#70941) on *MathOverflow* to Gil Kalai's community wiki question "[What is] [A Book You Would Like to Write](https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write)."

The extended answer seeks to link fundamental issues in TCS and QIT to practical issues in healing and regenerative medicine.

---

This answer extends [Peter Shor's answer](https://cstheory.stackexchange.com/questions/2074/physics-results-in-tcs/2407#2407), which discusses the roles of matrix product states in TCS and physics. Two recent surveys in the *Bulletin of the AMS* are relevant to matrix product states, and both surveys are well-written, free of pay-wall restrictions, and reasonably accessible to non-specialists:

* Joseph M. Landsberg's *[Geometry and the complexity of matrix multiplication](http://www.ams.org/journals/bull/2008-45-02/S0273-0979-08-01176-2/home.html)* (2008)
* Alvaro Pelayo's and San Vu Ngoc's *[Symplectic theory of completely integrable Hamiltonian systems](http://www.ams.org/journals/bull/2011-48-03/S0273-0979-2011-01338-6/home.html)*

The mathematical arena for Landsberg's survey is [secant varieties of Segre varieties](http://books.google.com/books?id=_XxZdhbtf1sC&pg=PA89), while the arena for Pelayo's and Ngoc's survey is four-dimensional symplectic manifolds … it takes awhile to appreciate that these two arenas both are matrix product states, as viewed respectively from a computational perspective (Landsburg) and a geometric perspective (Palayo and Ngoc). Moreover, Palayo and Ngoc include in their survey a discussion of Babelon, Cantini, and Douçot's *[A semi-classical study of the Jaynes–Cummings model](http://iopscience.iop.org/1742-5468/2009/07/P07011/)* (noting that the Jaynes–Cummings model is often encountered in the literature of condensed matter physics and quantum computing).

Each of these references goes far to illuminate the others. In particular, it has been helpful in our own (very practical) spin dynamical calculations to appreciate that the quantum state-spaces that are described variously in the literature as tensor network states, matrix product states, and secant varieties of Segre varieties are richly endowed with singularities whose algebraic, symplectic, and Riemannian structure is at present very incompletely understood (as Pelayo and Ngoc review).

For our engineering purposes, the [Landsburg/algebraic geometry approach](http://faculty.washington.edu/sidles/ENC_2011/index.html#burningArrow), in which the state-space of quantum dynamics is viewed as an algebraic variety rather than a vector space, is emerging as the most mathematically natural. This is surprising to us, but in common with many researchers, we find that the toolset of algebraic geometric is gratifyingly effective in validating and speeding practical quantum simulations.

Quantum simulationists presently enjoy the puzzling circumstance that large numerical quantum simulations very often perform much better than we have any known reason to expect. As mathematicians and physicists arrive at a shared understanding, this puzzlement surely will diminish and the enjoyment surely will remain. Good! :)


---

### Answer by username_15 on 2010-12-03. Score: 9

Early distributed systems theory, especially papers by Leslie Lamport et al., has had some impact from Special Relativity to get the correct picture w.r.t. to (fault-tolerant) agreement on a global system state. See entry 27. (*Time, Clocks and the Ordering of Events in a Distributed System*, Communications of the ACM 21, 7 (July 1978), 558-565) in the [Writings of Leslie Lamport](http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html), where Lamport gives the following background information on his paper:

> The origin of this paper was a note
> titled The Maintenance of Duplicate
> Databases by Paul Johnson and Bob
> Thomas. I believe their note
> introduced the idea of using message
> timestamps in a distributed algorithm.
> I happen to have a solid, visceral
> understanding of special relativity
> (see [5]). This enabled me to grasp
> immediately the essence of what they
> were trying to do. Special relativity
> teaches us that there is no invariant
> total ordering of events in
> space-time; different observers can
> disagree about which of two events
> happened first. There is only a
> partial order in which an event e1
> precedes an event e2 iff e1 can
> causally affect e2. I realized that
> the essence of Johnson and Thomas's
> algorithm was the use of timestamps to
> provide a total ordering of events
> that was consistent with the causal
> order. This realization may have been
> brilliant. Having realized it,
> everything else was trivial. Because
> Thomas and Johnson didn't understand
> exactly what they were doing, they
> didn't get the algorithm quite right;
> their algorithm permitted anomalous
> behavior that essentially violated
> causality. I quickly wrote a short
> note pointing this out and correcting
> the algorithm.


---

### Answer by username_17 on 2010-10-10. Score: 2

Much of the math that we use was originally invented to solve physics problems. Examples include calculus (Newtonian gravity) and Fourier series (heat equation).

> **Comments:**
> **username_18**: In a similar vein, Belkin, Narayanan and Niyogi (FOCS '06, http://dx.doi.org/10.1109/FOCS.2006.34) used mathematical analysis from the study of heat flow and diffusion to give a fast randomized algorithm for computing the surface area of a convex body in n dimensions.  
> **username_2**: good example. although is this an example of physics or mathematics ? :)  

---

### Answer by username_19 on 2021-01-08. Score: 2

I know some examples in machine learning. It is very common for thermodynamic ideas to be used in this area: [Boltzmann machine](https://en.wikipedia.org/wiki/Boltzmann_machine), [Hopfield network](https://en.wikipedia.org/wiki/Hopfield_network), [Wake-sleep algorithm](https://en.wikipedia.org/wiki/Wake-sleep_algorithm). [Markov Chain](https://en.wikipedia.org/wiki/Markov_chain) were initially used in physics, and today they have applications in reinforcement learning. And has a technique ([Momentum](https://en.wikipedia.org/wiki/Stochastic_gradient_descent#Momentum)) that is used to improve the optimization algorithm of gradient descedent, which is inspired by a concept that comes from mechanics.

The mathematical technique used in [Lagrangian Mechanics](https://en.wikipedia.org/wiki/Lagrangian_mechanics) are also used in [optimization](https://en.wikipedia.org/wiki/Lagrange_multiplier). As already stated, many ideas in mathematics were initially developed to solve physics problems.


---

### Answer by username_20 on 2014-04-25. Score: 2

There is a recent paper which establishes the connection between Computer Security and the 2nd principal of thermodynamic.  
<http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166>


---

### Answer by username_21 on 2013-01-21. Score: 1

The concept of potential is related to many different areas of physics. In cs, potential is used in amortized analysis of data structures. We can look at how each step affects the entropy of the system and therefore get an average (amortized) cost of an operation with a given data structure. This has given rise to many theoretically better data structures like the fibonacci heap.


---

### Answer by username_1 on 2013-01-23. Score: -1

to add/fill in some gap in the current excellent answers/coverage—there seems to be a strong connection between TCS and thermodynamics in various ways that hasnt yet been fully explored but is the frontiers of active research. there is a transition point associated with SAT but it seems possibly there are transition points associated with other (or even all) complexity classes as well. the SAT transition point is associated with a difference between "easy" (P) and "hard" (NP) instances, but arguably all complexity class boundaries must lead to the same transition point-like property.

consider a Turing Machine. it already measures its operation in normally *physical* dimensions of "time" and "space". but note that it apparently also does one unit of "work" in moving from square to square and making a transition. in physics the unit of work is Joules, which is also a measure of energy. so it appears that complexity classes have some relation to energy levels, boundaries, or regimes.

quantum mechanics theory increasingly sees space and time itself, the universe, as a sort of computing system. it appears it has some "minimal computation units" intrinsic to its nature, probably related to the Plank length. so examination of minimal Turing machines for problems also implies and relates to minimal physical/energy systems or even volumes of space required. [3]

also, the key concept of **entropy** shows up repeatedly in TCS and physics/thermodynamics and may be a unifying principle with still more active research revealing its underlying nature. [1,2]

[1] [entropy in information theory](http://en.wikipedia.org/wiki/Entropy_(information_theory)), wikipedia

[2] [what is the CS defn of entropy](https://stackoverflow.com/questions/510412/what-is-the-computer-science-definition-of-entropy), stackoverflow

[3] [What is the Volume of Information?](https://cstheory.stackexchange.com/questions/1593/what-is-the-volume-of-information) tcs.se

> **Comments:**
> **username_0**: You realise that I answered the tcs.se question, right?  
> **username_22**: I would like to understand why this question was downvoted. Downvoting without explanation helps no one, since the reasons can well be non technical. I understand that the OP was aware of some or all of this answer, but since he did not mention it in the question ...   cc @JoeFitzsimons  

---

