Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I try to understand if someone can apply a NTM to recognize 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 versus 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 assingment}

$\bar{SAT}$ = {$\varphi$: $\varphi$ is not satisfiable }

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 language of coNP can be solved by NTM just few of them, if yes, we will have intersection of NP class and coNP class. And if every language from coNP class cannot be solved by NTM, does it mean that limitation of NTM is located in coNP class. Is NTM is limited at all?

I am a little bit confused, I will appreciate if someone will shed the light on this topic.

share|improve this question
1  
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. –  Dave Clarke Nov 17 '12 at 17:52
    
@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? –  fog Nov 17 '12 at 19:00
    
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. –  Dave Clarke Nov 17 '12 at 19:03
    
@DaveClarke, thank you very much for the answer! –  fog Nov 17 '12 at 19:20

1 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.

share|improve this answer
    
Thank you very much for the answer –  fog Nov 18 '12 at 4:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.