2 ms·
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 establishe
by danbruc 4y ago
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.