3 ms·
I 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 co
by danbruc 10y ago
I 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.