0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your problem lies in the phrase "to solve a language". One does not solve a language, one recognises a language. Specifically, NP is about recognising whether a word is accepted by an NTM in polynomial-time. co-NP is, in essence, recongnising whether the word is rejected by an NTM in polynomial time. NP says nothing about the time taken to reject words. $\endgroup$ – Dave Clarke Nov 17 '12 at 17:52
  • $\begingroup$ @DaveClarke, thank you very much for the comment, I've edited the question. So all languages in coNP are recognized by NTM, if so, does NP and coNP intersect? $\endgroup$ – com Nov 17 '12 at 19:00
  • $\begingroup$ co-NP languages are certainly recognized by an NTM. But it is unknown whether it is a polynomial-time NTM. NP and co-NP certainly intersect: P, for example, lies in that intersection. $\endgroup$ – Dave Clarke Nov 17 '12 at 19:03
  • $\begingroup$ @DaveClarke, thank you very much for the answer! $\endgroup$ – com Nov 17 '12 at 19:20
4
$\begingroup$

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.

$\endgroup$

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.