What is the intuition behind EXPTIME being inside EXPSPACE?
When space complexity is usually smaller than time complexity or in the worse case, they are equal
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat is the intuition behind EXPTIME being inside EXPSPACE?
When space complexity is usually smaller than time complexity or in the worse case, they are equal
As Yuval Filmus states in the comments, any TM (with one tape and one read-write head) whose time complexity is bounded by a function $t$ also has its space complexity bounded by $t$ since, in $t$ steps, the TM can only scan as most as $t$ many tape positions. In terms of complexity classes: $$\textsf{TIME}(t) \subseteq \textsf{SPACE}(t)$$ $\textsf{P} \subseteq \textsf{PSPACE}$ and $\textsf{EXPTIME} \subseteq \textsf{EXPSPACE}$ is immediate from this. One of the greatest concerns of complexity theory (most of which are yet unsolved questions) is determining under which conditions this is a proper inclusion or not.
Think about it this way: Consider an algorithm that executes $n$ steps, and then stops. To make that happen - to execute exactly those $n$ steps - you first need some way to store the number $n$, and you also need some way to store every number from $1$ to $n$, as you will need to know either how many steps you've already taken, or how many steps you have left over, in order to say you need to stop.
It doesn't matter if the algorithm is or isn't literally a counter - for it to run that many steps, which can be thought of as somehow "encoded" within the input, it has to thus also somehow encode the same information that such a counter would within it somewhere, and thus it must demand at least $\lg n$ bits of storage.
Likewise, if you are only given $N$ bits of storage, you cannot have an algorithm that takes more than $n = 2^N$ steps and still terminate upon reaching that step, as it won't be able to "know", so to speak, how much further to run.
If you want to take more than $2^N$ steps and terminate, you must then need more storage. If you have storage that is exponential, i.e. $N = 2^M$, then you can now take doubly-exponential steps, i.e. $n = 2^{2^M}$. If your minimum running time is doubly-exponential, then it follows your minimum space must be exponential, just to store the information equivalent to that "counter".
Of course, the unresolved question is whether or not any problems which have solutions using exponentially growing amounts of space, can only have solutions which take super-exponential amounts of time, while the above only shows that if you have at least a doubly-exponential amount of time, you need an exponential amount of space, i.e. it's a sort of converse.