For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:


If $L \in NP $, then $ \bar{L} \in NP $


  • Let N be a non-deterministic Turing machine, which accepts L in polynomial time.

  • Swap all final states of $N$ with non-final states and vice-versa.

  • This new Turing machine $N'$ does now accept $\bar{L}$ in polynomial time.

Therefore $\bar{L} \in NP$

I have doubts that simply swapping non-final and final states within $N$ will produce a $N'$ with the proposed properties, but how can I show this?

  • $\begingroup$ This may be easier to think about if you imagine that $N$ first makes all of its non-deterministic choices and then does something deterministic. $\endgroup$
    – Louis
    Apr 17, 2016 at 15:02
  • $\begingroup$ Closely related question. $\endgroup$
    – Raphael
    Apr 17, 2016 at 16:39
  • $\begingroup$ Neither does the technique work for automata as simple as nondeterministic finite state automata. $\endgroup$ Apr 17, 2016 at 18:31

1 Answer 1


You just need to show that swapping final and non-final states doesn't complement the language accepted by an NTM, e.g., by showing that, for at least one NTM $N$ (which you can construct to have whatever properties you need), there is a string that is accepted by both $N$ and $N'$, or rejected by both.

  • $\begingroup$ How should I go about starting an argument like this? I neither have a precise definition of $N$ nor $L$, and since $N$ is nondeterminisitic I find it hard to understand how something like this would be stated. $\endgroup$
    – nitowa
    Apr 17, 2016 at 14:30
  • $\begingroup$ It's enough to do it for a particular $L$ and a particular $N$. $\endgroup$ Apr 17, 2016 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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