2
$\begingroup$

From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we have the following, where $n$ is the length of the input:

$$ \text{NP}=\bigcup \text{NTIME}(n^k) $$

This means that one way a problem can be shown to be $\in \text{NP}$ is if we can construct a non-deterministic TM $N$ using a polynomial time verifier $V$ on a certificate $C$, or:

TM $N$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$, accept

But if I use the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$, wouldn't this imply that $\text{co-NP} \subseteq \text{NP}$, since I can construct a TM $N'$ that can recognize co-NP:

TM $N'$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$ for any branch, reject
3. if all branches reject the guessed certificates, accept

In this case, since all branches of $N'$operate in polynomial time, $N'$ should also be able to solve problems for co-NP in non-deterministic polynomial time.

But since it is not yet sure if NP=co-NP, how should I understand the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$?

$\endgroup$
8
$\begingroup$

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine.

Rather, it's a "co-nondeterministic Turing machine" (if that were a term). Unsurprisingly, co-NP is exactly the set of languages accepted by some co-nondeterministic Turing machine, and the fact that NP=co-NP is open means exactly that it is not currently known whether nondeterministic and co-nondeterministic machines can compute the same things in polynomial time.

$\endgroup$
1
  • $\begingroup$ oh okay, that's a point I did not encounter in my texts. thanks ! $\endgroup$ – Link L Apr 18 '20 at 1:58

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.