1
$\begingroup$

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

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

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.

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

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.