3 ms·
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. Determi
by lambdaone 1y ago
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.
- tromp 1y agoNot 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 https://en.wikipedia.org/wiki/P-complete