3
$\begingroup$

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:

enter image description here

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

| cite | improve this question | |
$\endgroup$
3
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Logic Jun 12 '17 at 15:21
  • $\begingroup$ Each computation only follows one branch. You need to analyze what happens in each branch, and then take the maximum. $\endgroup$ – Yuval Filmus Jun 12 '17 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.