I was solving the following question:

Show that $L_1 \cap L_2 \in \mathrm{NP}$ for $L_1,L_2 \in \mathrm{NP}$.

I came a cross this solution on the internet which is:

$M$: On input $w$

  1. Run $M_1$ on $w$; if $M_1$ rejects then REJECT
  2. Else run $M_2$ on $w$; if $M_2$ rejects then REJECT
  3. Else ACCEPT

But is it the proof true? Are we allowed to state "if $M_1$ rejects then do something" knowing $M_1$ is a nondeterministic machine? Perhaps the following could be a correct solution:

$M$: on input $w$

  1. Run $M_1$ on $w$; if it accepts, then run $M_2$ on $w$; if it accepts, then ACCEPT

The reason I think the first solution is not true is that in the nondeterministic case, having a decider for a language $L$ does not imply a decider for the language $\overline{L}$ (right?); if the first solution were correct and $M$ were a decider for $L$, wouldn't $M'$, that simulate $M$ and only reverses the answer, be a decider for $\overline{L}$?

  • 1
    $\begingroup$ No, your solution is not correct. $L_1 \cap L_2$ only contains words that are both in $L_1$ and $L_2$. $\endgroup$
    – idmean
    Aug 3 '21 at 11:50
  • $\begingroup$ @idmean sorry i edited it. $\endgroup$
    – mike
    Aug 3 '21 at 11:58
  • $\begingroup$ @idmean no. my reason to think first one is not true is in non deterministic case having a decider for language $L$ does not imply a decider for language $\bar{L}$(right?). but why is that? if $M$ is a decider for $L$ isnt $M'$ that simply simulate $M$ and reverse the answer a decider for $\bar{L}$ $\endgroup$
    – mike
    Aug 3 '21 at 13:45
  • $\begingroup$ Yes, you're right, I made a mistake. Your algorithm is of course not equivalent to the first one. $\endgroup$
    – idmean
    Aug 3 '21 at 13:53
  • $\begingroup$ Both solutions are correct, if there is a branch s.t. both machines accept the input , obviously it would be found in nondeterministic algorithm that you described. And if w does not belong to both of languages obviously in first proof also it would be reject by one of the machines. $\endgroup$ Aug 11 '21 at 13:59

Both solutions are fine; in fact, they are equivalent.

A nondeterministic Turing machine for a language $L$ runs on an input $x$ and either accepts or rejects. If $x \in L$ then some run will accept, and if $w \notin L$ then all runs will reject. (Since the machine is nondeterministic, it can have several different runs on the same input.)

In your case, you are given nondeterministic machines $M_1,M_2$ for $L_1,L_2$, and on input $x$, you simply run both of them on $x$, and accept if both runs accept. If $x \in L_1 \cap L_2$ then some run of $M_1$ will accept and some run of $M_2$ will accept, and consequently some run of your machine will accept. If $x \notin L_1 \cap L_2$, then $x \notin L_1$ or $x \notin L_2$. If $x \notin L_1$ then no run of $M_1$ will accept, and consequently no run of your machine will accept; and similarly for the other case.

Another way to see that NP is closed under intersection is using witnesses. A language $L$ is in NP if there is a polytime machine $M$ and a polynomial $p$, accepting two inputs $x,w$, such that:

  • If $x \in L$ then $M$ accepts $(x,w)$ for some $w$ of length at most $p(|x|)$.
  • If $x \notin L$ then $M$ rejects $(x,w)$ for all $w$ of length at most $p(|x|)$.

You are given machines $M_1,M_2$ for the languages $L_1,L_2$, and you construct a new machine $M$ that accepts $(x,(w_1,w_2))$ if $M_1$ accepts $(x,w_1)$ and $M_2$ accepts $(x,w_2)$. You are simply providing witnesses for both machines $M_1,M_2$ at once. Moreover, you can choose $p(n) = p_1(n) + p_2(n) + 3$, where $p_1,p_2$ are the polynomials of $M_1,M_2$; this is still a polynomial.

To check your understanding, try to prove the following generalization. Let $L_1,\ldots,L_n \in \mathsf{NP}$, with characteristic functions $\chi_1,\ldots,\chi_n$, that is, $\chi_i(x) = 1$ if $x \in L_i$ and $\chi_i(x) = 0$ if $x \notin L_i$.

If $f\colon \{0,1\}^n \to \{0,1\}$ is any monotone function then the following language is in $\mathsf{NP}$: $$ \{x : f(\chi_1(x),\ldots,\chi_n(x)) = 1\}. $$ (Your case takes $f$ to be the binary AND function $f(x,y) = xy$.)

In contrast, $\mathsf{NP}$ is closed under $f(x) = 1-x$ iff $\mathsf{NP}=\mathsf{coNP}$, which most researchers consider unlikely.

Finally, what goes wrong with the solution that runs a nondeterministic machine for $L$ and reverses the output? Let $M$ be the machine for $L$, and let $M'$ be the new machine. Thus:

  • If $x \in L$ then $M$ accepts $x$ on some run, and so $M'$ rejects $x$ on some run.
  • If $x \notin L$ then $M$ rejects $x$ on all runs, and so $M'$ accepts $x$ on all runs.

As you can see, while $L(M')$ certainly contains $\overline{L}$, it could be larger; in fact, it could well consist of all words, since we can always modify $M$ to reject on some run.


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.