# Understanding of SPACE in non deterministic Turing Machines

Let's consider the following situation. We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$. I am trying to solve some problem and I am going to:

Generate every word using non-deterministic Turing Machine. And, for every generated word make a computation $C$. that uses only constant space and linear time. So, it seems that we have to remember (for a moment) generated word. I mean the situation that we have to generate word $w$ and then make a computation $C$ on $w$.

The scheme of Turing machine looks like:

The question is: Is my Turing machine NPSPACE? I have a problem with thinking about space complexity when it comes to nondterministic TM.

## 1 Answer

A nondeterministic Turing machine is a Turing machine that has a "guessing" mechanism. It accepts an input if there is a sequences of guesses that leads it to an accepting state. It rejects an input if all guesses lead it to a rejecting state.

The time complexity and space complexity of the Turing machine are defined in exactly the same way as for deterministic Turing machines:

• The time complexity on inputs of size $n$ is the maximum number of steps that the machine executes before halting over all inputs of size $n$ and all guesses.
• The space complexity on inputs of size $n$ is the maximum number of tape cells that the machine uses over all inputs of size $n$ and all guesses.

If your machine always uses only a polynomial amount of space, then it is is NPSPACE. Note that NPSPACE=PSPACE, a consequence of Savitch's theorem, and so you can convert it to a deterministic machine using polynomial space (the amount of space used could increase).

• Yes, but as you can see from my scheme my machine has a lot guesses. It branches exponentially. Every such branch uses polynomial space. The question is: Is it NPSPACE or not? – Logic Jun 12 '17 at 15:21
• Each computation only follows one branch. You need to analyze what happens in each branch, and then take the maximum. – Yuval Filmus Jun 12 '17 at 15:23