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
$\begingroup$
$\endgroup$
2
-
4$\begingroup$ A machine running in time $T$ uses up at most $T$ space. $\endgroup$ – Yuval Filmus Jul 3 '19 at 4:52
-
$\begingroup$ I'm hesitant to close as a duplicate but Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?) is essentially a slightly more complex version of the same thing. $\endgroup$ – David Richerby Jul 3 '19 at 10:21
Add a comment
|
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ If every algorithm that runs in time T, must run in space <= T, then shouldn't Space be inside of time? ie. since the space is dependent on time, shouldn't space be inside of time? $\endgroup$ – WeCanBeFriends Jul 3 '19 at 10:49
-
$\begingroup$ @WeCanBeFriends Let $S \in \textsf{TIME}(t)$. Then there is a TM $M$ which decides $S$ in time bounded by $t$. $M$ also has space bounded by $t$. Hence, $S$ can be decided in space bounded by $t$, that is, $S \in \textsf{SPACE}(t)$. $\endgroup$ – dkaeae Jul 3 '19 at 12:04
-
$\begingroup$ I don't understand how this shows that Time is contained in Space and not the other way around. What's the intuition for something being in EXPSPACE and not in EXPTIME? $\endgroup$ – WeCanBeFriends Jul 3 '19 at 12:45
-
$\begingroup$ @WeCanBeFriends It is a simple set inclusion argument; read it again with that in mind and you should be able to "get" it. The intuition for the classes possibly not being equal is that there may be problems which are decidable in exponential space but which are only decidable with strictly more than exponential time (though currently we do not know whether such problems exist); assuming inequality, an example would be any EXPSPACE-complete problem. $\endgroup$ – dkaeae Jul 3 '19 at 13:03
-
$\begingroup$ @user679128 Equality or not necessarily depends on $t$. If $t \in O(n)$, then we know $\textsf{TIME}(t) \neq \textsf{SPACE}(t)$ because $\textsf{TIME}(t)$ are the regular languages while $\textsf{SPACE}(t)$ are the context-sensitive languages. If $t$ grows faster than any computable function (e.g., the busy beaver function), then $\textsf{TIME}(t)$ and $\textsf{SPACE}(t)$ are equal because both are equal to the recursive languages (and the time and space bounds are irrelevant). $\endgroup$ – dkaeae Jul 3 '19 at 15:36
$\begingroup$
$\endgroup$
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.
