coNP and limitation of NDTM

Question

I am trying to understand if someone can apply an NTM to recognize a $coNP$ language.

From the definition we know that:

$NP$ - set of languages that can be recognized by NTM in polynomial time.

$coNP$ - set of all languages that are complement to $NP$ language.

as with $P$ vs. $NP$ question, we have $NP$ versus $coNP$ question.

Unfortunately, is not defined explicitly if can one recognize $coNP$ language with NTM.

However, if we take a look at few examples from the set of $coNP$ languages, few questions emerge.

$TAUTOLOGY$ = {$\varphi$: $\varphi$ is satisfied by every assignment}

$UNSAT$ = {$\varphi$: $\varphi$ is unsatisfiable}

These languages are known to be $coNP$ language and intuitively it seems like one can construct NTM to recognize these languages. On the other hand, if one can construct NTM to recognize them why them not in $NP$ class (by definition)? Maybe not all languages of $coNP$ can be solved by NTM, just few of them which are in $NP\cap coNP$. And if every language from $coNP$ class cannot be solved by NTM, does it mean that limitation of NTM is located in $coNP$. Does NTM have limitation at all?

I am a little bit confused, I would appreciate anyone that is willing to shine the light on this topic.

Answer 1

These complexity classes are not just defined by a machine model but also by the criteria about when a machine accepts a strings. So although $\mathsf{NP}$ and $\mathsf{coNP}$ can be defined using essentially the same underlining machine structure their accepting criteria are different. That is the main point you are missing.

In my experience, generally it is intuitively more clear for people to think about $\mathsf{NP}$ using its verifier-certificate definition and forget about the non-deterministic TM (which can be confusing).

We say a language $L$ is in $\mathsf{NP}$ if there is a polytime DTM with two inputs $V$ (think of $V$ as a certificate verifier) s.t. for all $x$, $ x \in L$ iff there exists a polynomial size certificate $y$ s.t. $V$ accepts $(x,y)$.

In more intuitive terms, $\mathsf{NP}$ is the set of problems that given an instance and a polysize solution/certificate/proof for that instance, we can efficiently verify the correctness of the given solution. E.g. given a graph and a list of vertices in it, it is possible in polynomial time to check if the list is a Hamiltonian path in the graph. Therefore Hamiltonian path problem is in $\mathsf{NP}$.

So in intuitive terms, $\mathsf{NP}$ is the set of problems that a given solution can be confirmed efficiently and $\mathsf{coNP}$ is the set of problems that a given solution can be refuted efficiently. For example, a refutation for a $TAUT$ instance is an assignment that makes the formula false.