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.

Image of NPComplete vs well-characterized

  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Feb 11, 2017 at 17:45
  • $\begingroup$ @D.W. Thanks for you advice, I edit my question a bit. $\endgroup$
    – Amir
    Commented Feb 11, 2017 at 21:32
  • $\begingroup$ 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... $\endgroup$
    – Heyheyhey
    Commented Feb 12, 2017 at 19:27

1 Answer 1


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.

  • 1
    $\begingroup$ Most people suspect this is not the case. $\endgroup$ Commented Feb 11, 2017 at 22:30
  • 1
    $\begingroup$ @YuvalFilmus What is your source for that? $\endgroup$
    – wogsland
    Commented Feb 12, 2017 at 4:22
  • 2
    $\begingroup$ It's common knowledge. In fact, most people believe the entire polynomial hierarchy to be strict. $\endgroup$ Commented Feb 12, 2017 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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