3 ms·
Thank you very much. This is much closer to what I had thought before I read what procrastitron said (though I was missing a number of the details such as thin
by drdeca 10y ago
Thank you very much.
This is much closer to what I had thought before I read what procrastitron said (though I was missing a number of the details such as things regarding NP vs co-NP ).
Thanks to you and Chinjut for clearing this up.
Also, this seems like this means that in my first comment
my statement of " if you've shown the problem to be in NP, then if it is NP-hard then [it is NP-complete]." was correct? (judging based on your statement that "A problem is NP-complete if it is NP-hard and in NP", which seems to roughly say what I said in my first comment).
Am I correct in thinking that these say basically the same thing?
- danbruc 10y agoI would say it is correct, it just seems a somewhat strange scenario to me. You know a problem is NP-hard and it of course has to be a decision problem or it could never end up in NP and then you show that it is indeed in NP, i.e. you show that it also has a polynomial time verifiable proof, which then makes the problem NP-complete. That does not sound impossible but I am not aware or can think of an example where it was hard to figure out that such a polynomial time proof is possible. I would love to know if there are examples but I really don't know.