DSPACE(f(n)) closed under complement

Question

I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$ does not change, therefore DSPACE($f(n)$) is closed under complement.

I know that most likely my answer is wrong. Can someone explain why?

Answer 1

Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).

In case your TMs are only defined as acceptors (i.e., a word not in the language will not necessarily be explicitly rejected, just not accepted), things are a bit more complex. In fact, we must then require more of $f$, namely that it is space-constructible; that is, given $n$ (unary encoded), we should be able to compute $f(n)$ (binary encoded) in space not greater than the value $f(n)$ itself. This property holds for practically all "standard" functions you know.

If that is the case, then, given a TM $A$ which accepts a language in space bounded by $f$, we proceed as follows:

1. Compute $f(n)$ (using $f(n)$ space).
2. Initialize a counter with the value $f(n)$. This counter need not use more space than what was already used in step 1; for example, we store it in a separate track of the TM tape.
3. Simulate $A$. For every step $A$ takes, decrement the counter. If the counter reaches zero, then enter the reject state (or loop without ever accepting).

This takes at most $f(n)$ space in steps 1 and 3 (and we reuse the tape in step 3), while step 2 does not take any additional space at all since representing the counter uses space on the order of $\log f(n)$, which is smaller than $f(n)$ (which is necessarily an integer), and we use a separate track for it.

Answer 2

Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,[8] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.

source