2 added 101 characters in body edited Jan 31 '18 at 15:49 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges Here's a TL;DR versionversion; I've also posted a longer answer to a similar question. Suppose we have a language $$A$$ that's decided in polynomial time by nondeterministic Turing machine $$M$$. The point is that $$x\in A$$ iff there $$M$$ has some accepting path on input $$x$$. However, since $$M$$ is nondeterministic, there may also be rejecting paths when it runs on $$x$$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language. It is this asymmetry of definition (accept if any path accepts; reject only if all paths reject) that makes the NP vs co-NP problem difficult. Here's a TL;DR version. Suppose we have a language $$A$$ that's decided in polynomial time by nondeterministic Turing machine $$M$$. The point is that $$x\in A$$ iff there $$M$$ has some accepting path on input $$x$$. However, since $$M$$ is nondeterministic, there may also be rejecting paths when it runs on $$x$$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language. It is this asymmetry of definition (accept if any path accepts; reject only if all paths reject) that makes the NP vs co-NP problem difficult. Here's a TL;DR version; I've also posted a longer answer to a similar question. Suppose we have a language $$A$$ that's decided in polynomial time by nondeterministic Turing machine $$M$$. The point is that $$x\in A$$ iff there $$M$$ has some accepting path on input $$x$$. However, since $$M$$ is nondeterministic, there may also be rejecting paths when it runs on $$x$$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language. It is this asymmetry of definition (accept if any path accepts; reject only if all paths reject) that makes the NP vs co-NP problem difficult. 1 answered Jan 31 '18 at 15:38 David Richerby 75k1616 gold badges117117 silver badges208208 bronze badges Here's a TL;DR version. Suppose we have a language $$A$$ that's decided in polynomial time by nondeterministic Turing machine $$M$$. The point is that $$x\in A$$ iff there $$M$$ has some accepting path on input $$x$$. However, since $$M$$ is nondeterministic, there may also be rejecting paths when it runs on $$x$$. If you just reverse the accepting and rejecting states, you'll go from a machine that had some accepting paths and some rejecting ones to a machine that has some rejecting paths and some accepting ones. In other words, it still has accepting paths, so it still accepts. Flipping the accept and reject states of a nondeterministic machine does not, in general, cause you to accept the complement language. It is this asymmetry of definition (accept if any path accepts; reject only if all paths reject) that makes the NP vs co-NP problem difficult.