Hacker News Reader

> we prove that flat origami, when viewed as a computational device, is Turing complete, or more specifically P-complete

...aren't those mutually exclusive?

I feel a mix of "those are obviously different complexity levels" and "is it like C pre-processor turing-completeness situation?"

View on HN

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.

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

Turing completeness and P completeness are completely different things. There is no sense in which P-completeness is a "more specific" version of Turing-completeness.

Reply on news.ycombinator.com