News for hackers. Stuff that matters.

A comment on Death Note: L, Anonymity and Eluding Entropy (2017). Parent comment

Re:Death Note: L, Anonymity and Eluding Entropy (2017) by the8472 on Monday August 05, 2019 @04:51PM (#20618787)
Time machines can be used as computers to reduce PSPACE (which includes NP) problems to constant time.
[ Parent | on HN ]
Re:Death Note: L, Anonymity and Eluding Entropy (2017) by lonelappde on Monday August 05, 2019 @09:12PM (#20621081)
Is polynomial space something to assume every time traveler has?

Even ones without a TARDIS?

[ Parent | on HN ]
Re:Death Note: L, Anonymity and Eluding Entropy (2017) by the8472 on Monday August 05, 2019 @09:19PM (#20621126)
PSPACE[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 [1] https://www.scottaaronson.com/papers/ctc.pdf

[ Parent | on HN ]