7
$\begingroup$

Currently 50 questions are tagged as [np-completeness] and 20 questions as [np-hardness]. Among them, 7 questions are tagged as both.

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:

  1. 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.
  2. 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.

$\endgroup$
8
  • 1
    $\begingroup$ I'd argue that np-completeness, while possibly less direct, is the more 'natural' tag. $\endgroup$ Nov 10 '10 at 5:59
  • $\begingroup$ I suggest keeping both tags. $\endgroup$ Nov 10 '10 at 12:29
  • $\begingroup$ @Suresh: I disagree. $\endgroup$
    – Jeffε
    Nov 10 '10 at 15:04
  • 1
    $\begingroup$ I'll make the change shortly. To repeat: this change will remove np-completeness, merging it completely into np-hardness $\endgroup$ Nov 10 '10 at 15:33
  • $\begingroup$ @Suresh: Yes, that is my intent of this proposal. $\endgroup$ Nov 10 '10 at 16:13
  • $\begingroup$ @Suresh: By merge, I meant also creating a tag synonym, if it was not clear. $\endgroup$ Nov 10 '10 at 16:30
  • $\begingroup$ ah it wasn't, because these are two separate operations. I'll do that as well. $\endgroup$ Nov 10 '10 at 16:36
  • $\begingroup$ @Suresh: Thanks! $\endgroup$ Nov 10 '10 at 18:16

You must log in to answer this question.

Browse other questions tagged .