# Well-Characterized vs NP-Complete

Definition: Well-Characterized also known as Good-Characterized is defined as follows:

Problem that have Yes and No certificates i.e., are in NP $\cap$ co-NP, are said to be Well-Characterized. (Reference: V.Vazirani, Approximation Algorithm)

Does exist any Well-Chracterized problem that is also being NP-Complete? I don't looking for any proof, I just want a real-world example of such problem.

• What do you mean by "well-characterized"? Can you give a definition? What are your thoughts? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Feb 11 '17 at 17:45
• @D.W. Thanks for you advice, I edit my question a bit. – Amir Feb 11 '17 at 21:32
• In its current form, the question may not be very interesting, but it seems to be more interesting to ask whether there exist a well-characterized problem that is not known to be in PTime? I am not aware of any such problem and I would very much like to learn more about this. One might think that some intermediate problems such as graph isomorphism (GI) are good candidates... However, although it is known that GI is in NP, it is open whether it is in coNP. Therefore, it maybe a good idea to also add this question... – Heyheyhey Feb 12 '17 at 19:27

We don't know. If any NP-complete problem were in co-NP, then we'd have NP$\,=\,$co-NP and we don't know whether that's true or not.