Hacker News Reader

My understanding of this is that P-completeness for a problem implies that any problem in P can be transformed into it with a polynomial-time reduction. Deterministic Turing machines (more precisely, the problem of determining the future state of a deterministic Turing machine) are in P.

View on HN

Not with a polynomial-time reduction though. Quoting from [1]:

> Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions.

[1] https://en.wikipedia.org/wiki/P-complete

Reply on news.ycombinator.com