Re:Rice’s Theorem: An interactive tutorial
by danbruc on Friday November 25, 2022 @09:55PM
(#33749430)
Simulating it step by step is the upper bound establishing that is in EXPTIME, the second part, the reduction to the bounded halting problem, is what establishes EXPTIME-completeness. And the time hierarchy theorem finally establishes that EXPTIME is not equal to P.
[ Parent
| on HN ]
There are no comments on this comment yet.