We don’t need no computation: why physicists should care about computational complexities

Kristina Šekrst
Centre for Croatian Studies; Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia

Computational complexity measures how much resources we need to solve a problem according to its inherent difficulty, and solution algorithms depend on the size of the problem. Recently, computational complexity has been applied to black hole radiation and similar issues in cosmology and astrophysics, where it seems that this kind of framework could allow general relativity and quantum mechanics to peacefully coexist, not by describing how the laws of physics behave, but by upholding them. This talk will try to demonstrate how the geometry of spacetime may be governed by computational complexity, which can be compared to the computational equivalent of the event horizons of black holes. Additional, the problem of computational barrier will be analyzed to see whether the category of computationally hard physical problems is generally unsolvable or only in principle, allowing specific instances that could break the presupposed constraints.