47
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 9
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Oct 10, 2010 at 2:50
  • $\begingroup$ I would think it counts. $\endgroup$
    – Joe Fitzsimons
    Oct 10, 2010 at 13:56
  • $\begingroup$ see also how are physics/CS getting united physics.se $\endgroup$
    – vzn
    Apr 27, 2014 at 15:33

17 Answers 17

Reset to default
27
$\begingroup$

The search technique simulated annealing is inspired by the physical process of annealing 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ supercooldave: My limited understanding was that simulated annealing only avoids local minima that are "sufficiently shallow." Is that correct? $\endgroup$
    – Joshua Grochow
    Oct 11, 2010 at 14:00
  • 1
    $\begingroup$ @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. $\endgroup$
    – Dave Clarke
    Oct 11, 2010 at 14:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Jul 15, 2011 at 21:25
  • $\begingroup$ 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. $\endgroup$
    – Elliot JJ
    Feb 19, 2012 at 23:19
23
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Oct 23, 2010 at 22:22
  • 5
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Oct 23, 2010 at 23:59
  • 1
    $\begingroup$ (@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. cstheory.stackexchange.com/questions/2074/… $\endgroup$
    – John Sidles
    Jul 15, 2011 at 21:24
20
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm developing quite a strong interest in networks and social network analysis. Do you have any references? $\endgroup$
    – Dave Clarke
    Jun 13, 2011 at 17:03
  • 2
    $\begingroup$ 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 $\endgroup$
    – Suresh Venkat
    Jun 14, 2011 at 9:33
19
$\begingroup$

A result of Pour-El and Richards Adv. Math. 39 215 (1981) 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I would also mention DNA computing as an area of overlap, albeit with more tenuous connections to theoretical physics per se. $\endgroup$
    – S Huntsman
    Oct 10, 2010 at 2:08
  • 1
    $\begingroup$ I more had in mind areas where TCS benefited from results in physics, rather than the other way around. $\endgroup$
    – Joe Fitzsimons
    Oct 10, 2010 at 12:49
  • 7
    $\begingroup$ 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. $\endgroup$
    – S Huntsman
    Oct 10, 2010 at 17:34
  • $\begingroup$ 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. $\endgroup$
    – S Huntsman
    Oct 10, 2010 at 17:45
17
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Oct 11, 2010 at 12:05
14
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ What about analytic combinatorics (Flajolet and Sedgewick)? $\endgroup$
    – RJK
    Oct 11, 2010 at 13:08
11
$\begingroup$

Gauge Theory for heuristic approximations to integer programming (a few of Misha Chertkov's 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.

Improve this answer
$\endgroup$
10
$\begingroup$

Statistical physics has given computer scientists a novel way of looking at SAT, as overviewed here. 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yikes, I just realized that Joe referenced this in his original question. Hopefully this elaborates a bit. $\endgroup$
    – Huck Bennett
    Dec 3, 2010 at 7:46
10
$\begingroup$

Force-based graph drawing algorithms 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$
    – Joe Fitzsimons
    May 25, 2011 at 14:13
  • $\begingroup$ Graphs are surely TCS. And they need to be drawn. And David Eppstein does graph drawing. (This is my compelling argument.) $\endgroup$
    – Dave Clarke
    May 25, 2011 at 14:17
  • $\begingroup$ Ok, I'll accept that argument. $\endgroup$
    – Joe Fitzsimons
    May 25, 2011 at 14:21
  • $\begingroup$ This technique is a major player in graph drawing. definitely worth mentioning $\endgroup$
    – Suresh Venkat
    May 25, 2011 at 14:34
  • $\begingroup$ Great example! +1 from me $\endgroup$
    – George
    Jul 22, 2011 at 21:29
9
$\begingroup$

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, 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.

Improve this answer
$\endgroup$
9
$\begingroup$

I have fleshed-out this answer with an extended answer on MathOverflow to Gil Kalai's community wiki question "[What is] 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, 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:

The mathematical arena for Landsberg's survey is secant varieties of Segre varieties, 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 (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, 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! :)

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 7
    $\begingroup$ In a similar vein, Belkin, Narayanan and Niyogi (FOCS '06, 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. $\endgroup$
    – arnab
    Oct 10, 2010 at 17:33
  • 2
    $\begingroup$ good example. although is this an example of physics or mathematics ? :) $\endgroup$
    – Suresh Venkat
    Oct 10, 2010 at 17:35
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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 in physics, and today they have applications in reinforcement learning. And has a technique (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 are also used in optimization. As already stated, many ideas in mathematics were initially developed to solve physics problems.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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, wikipedia

[2] what is the CS defn of entropy, stackoverflow

[3] What is the Volume of Information? tcs.se

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You realise that I answered the tcs.se question, right? $\endgroup$
    – Joe Fitzsimons
    Jan 23, 2013 at 15:03
  • $\begingroup$ 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 $\endgroup$
    – babou
    Apr 27, 2014 at 11:50

Your Answer

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

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