Showing NP is closed under intersection

Question

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

Answer 1

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.