Showing NP is closed under intersection

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}$$?

• No, your solution is not correct. $L_1 \cap L_2$ only contains words that are both in $L_1$ and $L_2$. Aug 3 '21 at 11:50
• @idmean sorry i edited it.
– mike
Aug 3 '21 at 11:58
• @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}$
– mike
Aug 3 '21 at 13:45
• Yes, you're right, I made a mistake. Your algorithm is of course not equivalent to the first one. Aug 3 '21 at 13:53
• 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. 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.