3 ms·
Sorry, you are wrong. Your description of ${CLASS}-hard is precisely backwards. For example, see Wikipedia: https://en.wikipedia.org/wiki/NP-hardness https://en
by Chinjut 10y ago
Sorry, you are wrong. Your description of ${CLASS}-hard is precisely backwards. For example, see Wikipedia: https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
"NP" itself already means "No harder than NP-complete" [under Karp reduction; Cook reduction perhaps tracks ordinary language "hard" better, but, whatever]. "NP-hard" means "No easier than NP-complete". "NP-complete" means, well, "Exactly as easy as NP-complete" [again, under Karp reduction].
- procrastitron 10y agoYou are right; I got it backwards.