Black Holes and Complexity Classes

Understand

It is not known what the limitations are on using quantum computation to speed up classical computation.

• An example would be the power to speed up PSPACE-complete computations.
• It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes.
• What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers.