what can be said about complexity of “typical” supercomputing programs/ applications? any NP hard?

Question

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(n³) where n is the grid distance/ length. molecular dynamics simulations have O(n²) calculations where n is the number of particles. many other calculations are done on matrices which are typically O(n²). etc. (not sure about fluid dynamics simulations.) PageRank might be 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" where there is questions about using supercomputers for theorem proving in the comments etc.)

Answer 1

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, a short overview of 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 are an example of an explicit theoretical framework showing which hints are needed for shifting some problems to more tractable complexity classes.