0
$\begingroup$

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:

Lemma:

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

Proof:

  • 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?

$\endgroup$
  • $\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 '16 at 15:02
  • $\begingroup$ Closely related question. $\endgroup$ – Raphael Apr 17 '16 at 16:39
  • $\begingroup$ Neither does the technique work for automata as simple as nondeterministic finite state automata. $\endgroup$ – Hendrik Jan Apr 17 '16 at 18:31
4
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 14:30
  • $\begingroup$ It's enough to do it for a particular $L$ and a particular $N$. $\endgroup$ – Yuval Filmus Apr 17 '16 at 18:47

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.