top | item 8051238

(no title)

sidww2 | 11 years ago

"only" NP-hard? You know that NP-hard problems are equal to order harder than NP-complete ones, right?

discuss

Strilanc|11 years ago

Probably referring to the definition, not the difficulty.

codeflo|11 years ago

Yes, NP-complete is a subset of NP-hard. Grandparent states that NP-completeness only applies to decision problems (which is correct), but seems to think that NP-hardness applies to optimization problems (which is incorrect; NP-hard too is a class of decision problems).

brockrockman|11 years ago

didn't mean to imply "only" as a less-than comparison -- just a distinction.