Proof of `The inclusion chain of complexity classes` (4th statement)
groundedproofs/Lax434930Proofs/NPSpaceExponentialTime.lean · lax-434930
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 5 of this submission's paper
Description
Apply the proved Savitch simulation, bound the deterministic machine's run length by its configuration count, and use the time-bounded stack and tape simulations.