2 ms·
Time machines can be used as computers to reduce PSPACE (which includes NP) problems to constant time.
by the8472 7y ago
Time machines can be used as computers to reduce PSPACE (which includes NP) problems to constant time.
- lonelappde 7y agoIs polynomial space something to assume every time traveler has? Even ones without a TARDIS?
- the8472 7y agoPSPACE[0] is a computational complexity class, not about topology ("larger on the inside"). Any timemachine that produces self-consistent timelines (arrives at a fixed point after a finite amount of iterations) can be used to solve problems in PSPACE.[1] [0] https://en.wikipedia.org/wiki/PSPACE https://en.wikipedia.org/wiki/PSPACE [1] https://www.scottaaronson.com/papers/ctc.pdf https://www.scottaaronson.com/papers/ctc.pdf