I think that the difference of these two tags is too subtle for the distinction to be useful. Therefore, I propose to merge [np-completeness] to [np-hardness]. Note the direction; I am proposing to make the more popular tag a synonym for the less popular tag, which is different from the usual proposal.
I know that NP-completeness and NP-hardness are two different notions. However, in most cases, questions tagged as [np-completeness] ask whether a certain problem which is trivially in NP is NP-complete or not. Therefore, the main point is whether the problem is NP-hard or not. On the other hand, some of the questions tagged as [np-hardness] are about search or optimization problems, which are themselves not in NP (according to the standard definition of NP as a class of decision problems). But the difference between search/optimization problems and decision problems is a technicality in most cases and should not be important in the classification of questions.
Some questions tagged as [np-hardness] ask about problems which are not known to be in NP. Therefore, merging in the other direction would make the tag awkward for some questions.
What do you think?
Update: It has reached +4 with 4 upvotes and 0 downvotes, but there are two negative comments. What should I do? Let me clarify my points:
- We should merge [np-completeness] and [np-hardness] into one tag because for most questions, their distinction depends not on the essence of a question but on a particular way a question is stated.
- We should not merge them into [np-completeness] because there are rare cases where the [np-completeness] tag would be awkward.
If merging the two into the [np-hardness] tag is not desired, an alternative suggestion is to merge them into a new tag, for example [np-complete-np-hard]. But this is certainly clumsy.