Why can't we say that NP is closed under complement given that we can say it is closed under intersection

Question

I found online solutions which prove the closure of NP under intersection in the following way: given machines $M_1,M_2$ for accepts nondeterministically languages $L_1,L_2$, we construct the following machine $M$ which accepts nondeterministically $L_1 \cap L_2$:

$M$ = ”On input $w$:

1. Run $M_1$ on $w$. If $M_1$ rejected then reject.

2. Else run $M_2$ on $w$. If $M_2$ rejected then reject.

3. Else accept."

Is this proof correct? Can't we use similar ideas to show that NP is closed under complementation, which is supposedly an open problem?

Answer 1

There are several ways to describe the semantics of nondeterministic Turing machines. Perhaps the most colorful is the "guess and verify" semantics. We enhance a vanilla Turing machines with a guess tape, whose exact semantics will be explained below. Our Turing machine communicates its computation with the user by means of the state at which it halts. Some states are marked ACCEPT, the rest are marked REJECT. The semantics of the machine are as follows:

A nondeterministic machine accepts an input $x$ if there exists a string $y$ such that if we run the machine with $x$ on the input tape and $y$ on the guess tape, then it accepts (i.e., halts at a state marked ACCEPT).

Conversely, the machine rejects an input $x$ if whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tape, it always rejects (i.e., halts at a state marked REJECT), whatever we wrote on the guess tape.

A nondeterministic machine accepts a language $L$ if it accepts all $x \in L$ and rejects all $x \notin L$.

A nondeterministic machine runs in polynomial time (polytime for short) if there is a polynomial $p(n)$ such that whenever we run the machine with $x$ on the input tape and arbitrary contents on the guess tapes, it always halts within $p(|x|)$ steps.

(We are slightly cheating here: the definitions of acceptance and rejection are complementary only if the machine is promised to always halt, which is indeed the case for machines running in polynomial time.)

---

When describing the operation of a nondeterministic machine, we will often use the keywords "guess" and "verify". They have the following meaning:

1. Guess $w$: Copy a string $w$ (delimited in some fixed way) from the guess tape to the work tape.
2. Verify property $A$: Check whether property $A$ holds. If so, continue with the execution of the algorithm. Otherwise, halt at once at a state marked REJECT.

Another important convention is:

• If the algorithm runs its course without rejecting, then the machine halts at a state marked ACCEPT.

Here is an example, a machine for SAT:

Input: A formula $\varphi$ in conjunctive normal form.

Operation: Guess an assignment $a$, and verify that it is a satisfying assignment.

A more exact description of the machine would be:

1. Copy an assignment $a$ from the guess tape to the work tape.

2. Check whether $a$ satisfies $\varphi$.

3. If $a$ doesn't satisfy $\varphi$, halt at a state marked REJECT.

4. Otherwise, halt at a state marked ACCEPT.

---

Let us now consider the proof that NP is closed under intersection. Let $M_1,M_2$ be polytime nondeterministic Turing machines accepting languages $L_1,L_2$ (respectively). The following polytime nondeterministic Turing machine $M$ accepts $L_1 \cap L_2$:

1. Verify that $M_1$ accepts the input.
2. Verify that $M_2$ accepts the input.

In more detail:

1. Decode the contents of the guess tape into two guess words.
2. Run $M_1$ on the inputs and the first guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
3. Run $M_2$ on the inputs and the second guess word. If it halts at a state marked REJECT, enter a state marked REJECT and halt.
4. Enter a state marked ACCEPT and halt.

Why does this work? Let $L$ be the language accepted by this machine. We have to show that $L = L_1 \cap L_2$.

1. $L_1 \cap L_2 \subseteq L$: Suppose that $x \in L_1 \cap L_2$. Since $x \in L_1$, there exists a string $y_1$ such that $M_1$ accepts when run on $x$ with $y_1$ on the guess tape. Similarly, since $x \in L_2$, there exists a string $y_2$ such that $M_2$ accepts when run on $x$ with $y_2$ on the guess tape. If we run $M$ on $x$ with $(y_1,y_2)$ on the guess tape, then it will accept, and so $x \in L$.

2. $L \subseteq L_1 \cap L_2$: Suppose that $x \in L$. Thus there is a string $y = (y_1,y_2)$ such that when $M$ is run on the input $x$ and $y$ on the guess tape, it accepts. The machine $M$ verifies that $M_1$ accepts when run on the input $x$ and $y_1$ on the guess tape, and that $M_2$ accepts when run on the input $x$ and $y_2$ on the guess tape. Therefore $x \in L_1$ and $x \in L_2$, and so $x \in L_1 \cap L_2$.

---

Now let us try to prove that NP is closed under complementation. Let $M$ be a polytime nondeterministic Turing machine accepting a language $L$. We construct the following Turing machine $M'$:

Run $M$. If $M$ accepts, reject. Otherwise, accept.

Let us see what are the semantics of this machine. The machine $M'$ accepts an input $x$ if there exist a string $y$ such that when running $M$ on $x$ with $y$ on the guess tape, it rejects. Conversely, the machine $M'$ rejects an input $x$ if $M$ accepts $x$ regardless of the contents of the guess tape.

This is not quite what we want, and to demonstrate it, let us consider the machine $M$ accepting SAT described above. Recall that the machine interprets its input as a formula $\varphi$, and the contents of the guess tape as an assignment $a$. The machine $M$ accepts iff $a$ satisfies $\varphi$. The corresponding machine $M^c$ has the following semantics:

1. The machine $M^c$ accepts a formula $\varphi$ if some assignment $a$ doesn't satisfy $\varphi$.

2. The machine $M^c$ rejects a formula $\varphi$ if all assignments $a$ satisfy $\varphi$.

In other words, the machine $M^c$ accepts the language of all formulas which are not tautologies. This is not what we were aiming for: we wanted $M^c$ to accepts the language of all unsatisfiable formulas. As an example, $M^c$ accepts the formula $x_1 \lor x_2$ even though it is satisfiable, because it's not a tautology (if $x_1$ and $x_2$ are both false then $x_1 \lor x_2$ is also false).

Answer 2

Nondeterministic Turing Machines don't technically reject. They accept or run indefinitely. You can also not abort that. It's a very subtle difference with a lot of impact. Otherwise indeed it would be that NP=co-NP

As was noted, this is the in model that I learned. Other models are possible, where the Nondeterministc machine does halt even when rejecting (see Yuval's answer). Also in such models, NP is not closed under complement.

Answer 3

I prefer representing languages by their decision problems, i.e. Boolean functions $2^*\to 2$, i.e. the language $L = \{x\in 2^*\mid \varphi(x)\}$ and $\varphi(x)\iff x\in L$ converts between these two representations. That given languages $L_1, L_2\in\mathbf{NP}$, $L_1\cap L_2\in\mathbf{NP}$ looks like: given $\varphi,\psi\in\mathbf{NP}$, $\varphi\land\psi\in\mathbf{NP}$.

By (one) definition, $\varphi\in\mathbf{NP}$ if and only if there is a polynomial-time Turing machine (TM) $M$ and a polynomial $p$ such that for all $x\in2^*$, $$\varphi(x)\iff\exists u\in 2^{p(|x|)}.M(x,u)=1$$ where $|x|$ is the length of the bitstring $x$. The reason the conjunction of $\varphi_1$ and $\varphi_2$ is in $\mathbf{NP}$ is because if for each $x\in 2^*$, there exist TMs $M_i$, polynomials $p_i$, and $u_i\in 2^{p_i(|x|)}$ such that $\varphi_i(x) \iff M_i(x,u_i)=1$, then $u_1u_2\in 2^{q(|x|)}$ where $q(X) = p_1(X)+p_2(X)$ is a polynomial such that $\varphi_1(x)\land\varphi_2(x) \iff M(x,u) = 1$ where $M$ is the TM that extracts the first $p_1(|x|)$ bits of $u$ which is $u_1$ and simulates $M_1(x,u_1)$, then extracts the remaining $p_2(|x|)$ bits of $u$ which is $u_2$ and simulates $M_2(x,u_2)$ and returns $1$ if each of these return $1$. $M$ runs in polynomial-time if $M_1$ and $M_2$ do.

So why doesn't a similar approach work for the complement, i.e. for calculating $\neg\varphi(x)$? Let's logically manipulate the definition of $\mathbf{NP}$ a bit. Negating both sides of the $\iff$ gives $$\neg\varphi(x)\iff\forall u\in 2^{p(|x|)}.M(x,u)=0$$ So the issue is while for $\varphi\in\mathbf{NP}$ there is for every $x\in 2^*$ some TM $M$, polynomial $p$, and $u\in 2^{p(|x|)}$ such that $M(x,u)=1 \implies \varphi(x)$, for $\neg\varphi$ to be in $\mathbf{NP}$ we'd need $M(x,u) = 1 \implies \varphi(x)$ for all $u\in 2^{p(|x|)}$ which is to say $M$ would need to decide membership for $x$ without using anything (except perhaps the length) about $u$. This certainly isn't the case for all TMs witnessing membership in $\mathbf{NP}$. Therefore, we can't use an arbitrary witness that $\varphi\in\mathbf{NP}$ to build a witness that $\neg\varphi\in\mathbf{NP}$ simply by simulating $M$ and negating the result. This doesn't rule out that we can't find other TMs to witness $\neg\varphi\in\mathbf{NP}$; just that the TM that simulates $M$ and negates its output doesn't work in general.

Answer 4

The definition of NP is not symmetric.

The definition of a decision problem in NP is: "If the answer for an instance is YES, then there is polynomial time proof that the answer is YES". (Or: There is a hint that can be checked in polynomial time. Or: There is a non-deterministic machine that finds a proof in polynomial time. All equivalent).

The existence of a simple proof if the answer is YES doesn't imply the existence of a a simple proof if the answer is No.

Take the problem "Is there a mouse in my house"? If the answer is YES, there is a very simple proof: Just grab it by its tail. The proof may be hard to find, but once you found it it is easy to check. If the answer is NO, you'll have to search the whole house with all its tiny little corners for the mouse, and then you have to search again because it could have moved to a room that you already searched. So for the answer YES there is a simple proof, for the answer NO there isn't.

Or the Travelling Salesman Problem: Given a set of cities and their distances, is there a way to visit each city once, with a total distance less than 1,000 miles? If the answer is YES, I'll give you a list of cities with total distance less than 1,000 miles, and you have your proof. Easy to check. If there is no such city, then one proof would be to check all possible cycles and check that none had a distance less than 1000. The proof is an awful lot harder.