<p>The manufacturers of the computing hardware themselves are their own customers, and use supercomputing to approximatively solve a number of well-know and more obscure NP-hard tasks. One of the oldest and best-known is <a href="https://en.wikipedia.org/wiki/Place_and_route" rel="nofollow">place-and-route</a>, a short overview of <a href="https://en.wikipedia.org/wiki/Electronic_design_automation" rel="nofollow">electronic design automation</a> reveals many more NP-hard tasks.</p>

<p>Often the employed algorithms are true NP algorithms, whose success (or approximation quality) depend crucially on <em>additional</em> hints directly and indirectly provided. A typical indirect hint is the hierarchical structure used for <em>compression</em> in the input file formats. A direct hint might be given by restricting the range of some parameter which is optimized, but the need and possibility for giving hints can go far beyond that.</p>

<p>Rather than dismissing those hint as cheating and semi-automation, it can make sense to explicitly acknowledge the need for those hints. <a href="https://www.cis.upenn.edu/~alur/nw.html" rel="nofollow">Nested Words and Visibly Pushdown Languages used for Program Analysis</a> are an example of an explicit theoretical framework showing which hints are needed for shifting some problems to more tractable complexity classes.</p>

CC BY-SA 3.0
2015-08-02T09:35:14.170Z
2015-08-02T09:35:14.170Z
Thomas Klimpel
<p>To comment on the mentioned runtime of molecular dynamics simulations.
You will only have O(n²) in a naive implementation evaluating all possible pair interactions. Most of the used frameworks (GROMACS, Amber, OpenMM, probably also NAMD) use the particle mesh ewald method to calculate the long-range interactions, which uses FFT. Since this part of the computation is by far the dominating part you effectively have O(n*log(n)) instead. There are many publications about this, see for example <a href="https://doi.org/10.1063/1.464397" rel="nofollow noreferrer">https://doi.org/10.1063/1.464397</a>. Furthermore, there is the fast multipol method that even has O(n) for the long-range interactions, although this method requires the system to be large in order to be superior. For an implementation of this method in GROMACS, see here: <a href="https://pubs.acs.org/doi/10.1021/acs.jctc.0c00744" rel="nofollow noreferrer">https://pubs.acs.org/doi/10.1021/acs.jctc.0c00744</a>.</p>

CC BY-SA 4.0
2024-12-07T17:24:16.953Z
2024-12-07T17:24:16.953Z
mithrawnuruodo
<p>supercomputers have risen dramatically in their computational powers last few decades due to Moore's law &amp; also increasing parallelism technology in hardware and software. many different types of analysis algorithms are run now for many diverse areas of science.</p>

<blockquote>
  <p>what can be said about the complexity of typical supercomputing jobs/ applications? are they "mostly" in P? are there examples of major supercomputing projects that tackle NP hard problems or harder? is there some published study/ survey of the complexity of supercomputing problems?</p>
</blockquote>

<p>my (rough) understanding is that maybe "most" are in P. for example "grid" calculations for 3d volumes are typically something like <em>O(n<sup>3</sup>)</em> where <em>n</em> is the grid distance/ length. molecular dynamics simulations have <em>O(n<sup>2</sup>)</em> calculations where <em>n</em> is the number of particles. many other calculations are done on matrices which are typically <em>O(n<sup>2</sup>)</em>. etc. (not sure about fluid dynamics simulations.) PageRank <a href="https://stackoverflow.com/questions/12474398/what-is-pageranks-big-o-complexity">might be</a> O(n) or at least Ptime.</p>

<p>(this question is partly motivated by discussion on Aaronsons blog/ comments <a href="http://www.scottaaronson.com/blog/?p=2408" rel="nofollow noreferrer">"introducing some British people to P vs NP"</a> where there is questions about using supercomputers for theorem proving in the comments etc.)</p>

<reference-request><big-picture><application-of-theory><p-vs-np><ar.hardware-architecture>
what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?
vzn
# what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

(Asked by: username_0 on 2015-07-31)

supercomputers have risen dramatically in their computational powers last few decades due to Moore's law & also increasing parallelism technology in hardware and software. many different types of analysis algorithms are run now for many diverse areas of science.

> what can be said about the complexity of typical supercomputing jobs/ applications? are they "mostly" in P? are there examples of major supercomputing projects that tackle NP hard problems or harder? is there some published study/ survey of the complexity of supercomputing problems?

my (rough) understanding is that maybe "most" are in P. for example "grid" calculations for 3d volumes are typically something like *O(n3)* where *n* is the grid distance/ length. molecular dynamics simulations have *O(n2)* calculations where *n* is the number of particles. many other calculations are done on matrices which are typically *O(n2)*. etc. (not sure about fluid dynamics simulations.) PageRank [might be](https://stackoverflow.com/questions/12474398/what-is-pageranks-big-o-complexity) O(n) or at least Ptime.

(this question is partly motivated by discussion on Aaronsons blog/ comments ["introducing some British people to P vs NP"](http://www.scottaaronson.com/blog/?p=2408) where there is questions about using supercomputers for theorem proving in the comments etc.)

**Tags:** reference-request, big-picture, application-of-theory, p-vs-np, ar.hardware-architecture


---

## 2 answers

### Answer by username_1 on 2015-08-02. Score: 4 | Accepted answer

The manufacturers of the computing hardware themselves are their own customers, and use supercomputing to approximatively solve a number of well-know and more obscure NP-hard tasks. One of the oldest and best-known is [place-and-route](https://en.wikipedia.org/wiki/Place_and_route), a short overview of [electronic design automation](https://en.wikipedia.org/wiki/Electronic_design_automation) reveals many more NP-hard tasks.

Often the employed algorithms are true NP algorithms, whose success (or approximation quality) depend crucially on *additional* hints directly and indirectly provided. A typical indirect hint is the hierarchical structure used for *compression* in the input file formats. A direct hint might be given by restricting the range of some parameter which is optimized, but the need and possibility for giving hints can go far beyond that.

Rather than dismissing those hint as cheating and semi-automation, it can make sense to explicitly acknowledge the need for those hints. [Nested Words and Visibly Pushdown Languages used for Program Analysis](https://www.cis.upenn.edu/~alur/nw.html) are an example of an explicit theoretical framework showing which hints are needed for shifting some problems to more tractable complexity classes.


---

### Answer by username_2 on 2024-12-07. Score: 0

To comment on the mentioned runtime of molecular dynamics simulations.
You will only have O(n²) in a naive implementation evaluating all possible pair interactions. Most of the used frameworks (GROMACS, Amber, OpenMM, probably also NAMD) use the particle mesh ewald method to calculate the long-range interactions, which uses FFT. Since this part of the computation is by far the dominating part you effectively have O(n\*log(n)) instead. There are many publications about this, see for example <https://doi.org/10.1063/1.464397>. Furthermore, there is the fast multipol method that even has O(n) for the long-range interactions, although this method requires the system to be large in order to be superior. For an implementation of this method in GROMACS, see here: <https://pubs.acs.org/doi/10.1021/acs.jctc.0c00744>.


---

