Let's define:
$Disagree(M_1,M_2) = \{x| $The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$

that means: if $M_1$ accept, $M_2$ reject and vice versa

$NPA=\{L|\exists M_1,M_2$ Nondeterministic polynomial TM $ s.t. Disagree(M_1,M_2)=L\}$

Is $NPA=R$?

I thought about this problem from 2 clashing ways:

  1. If I choose $M_1$ to accept any input and $M_2$ to reject any input, for given $L$ each $x\in L$ will be $x\in Disagree(M_1,M_2)$ so $NPA=R$
  2. To accept $L$, $M_1$ and $M_2$ should run on every $x\in L$ and even if it's a single step the input ($L$) is a countably infinite set, so it's impossible to run on all the $x\in L$, so $NPA\neq R$

When I saw the answer, I understood that both of my ways wrong, but I can't understand in which step?

  • $\begingroup$ What answer did you see? Where does it disagree with your work? It might be that both are right... $\endgroup$ – vonbrand Jan 19 at 12:56

I'll assume that $R$ is the set of recursive languages and that in the definition of $NPA$ we are talking about Nondeterministic Polynomial Time.

  1. You are just proving that, for $L \in R$, $L \subseteq Disagree(M_1, M_2)=\Sigma{}^*$ which says nothing about $NPA = R$.

  2. To accept a language $L$, there must be some machine $M$ such that for each string $x \in L$ the computation $M(x)$ halts in the accepting state and for each string $x \not\in L$ the computation $M(x)$ does not halt. To decide a language $L$, the machine must halt in all inputs and, furthermore, if $x \in L$ the machine halts in accepting state, otherwise the machine halts in rejecting state. That doesn't mean that the machine is "tested" simultaneously on an infinite number of strings.

That being said, when you want to prove that two sets are equal you need to prove that each one includes the other. When you want to prove that two sets are different, it is sufficient to find some language that is in one set but non the other.

In your case, the requirement that $M_1, M_2$ must halt in a polynomial number of steps is suspicious.

If $L \in NPA$, then there are Nondeterministic machines $M_1, M_2$ such that they both halt in a polynomial number of steps and disagree precisely on $L$. From those machines, you can construct a Nondeterministic machine $M_{1,2}$ that decides $L$ in polynomial time, hence $L \in \mathcal{NP}$ and this proves the inclusion $NPA \subseteq \mathcal{NP}$ by generality of $L$.

By the Time Hierarchy Theorem, $$NPA \subseteq \mathcal{NP} \subsetneq \mathcal{N}EXP \subseteq R$$

Hence $NPA \neq R$.


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.