2

So I normally peruse questions, and recently got tag-editing capability. I noticed that sometimes folks like to tag the common abbreviation of to . OK, simple, ask meta to synonymize it, right?

Maaaybe not. As per 's tag wiki:

NP ("nondeterministic polynomial") is a complexity class of decision problems that can be solved by a nondeterministic Turing machine in polynomial time. Equivalently, it is the set of decision problems for which an answer can be verified in polynomial time by a deterministic Turing machine.

Wait, is that even on-topic? There seems to be quite a few questions and answers in along those lines, and I don't know enough theoretical CS to judge, so I'm bringing it to meta!

Basically I see 3 options:

  1. NP-complexity is off-topic for SO, and therefore burninate questions on it and then synonimize with
  2. NP-complexity is on-topic for SO, but rare/esoteric enough to justify renaming to and then synonimizing with or burninating entirely.
  3. Do nothing, retagging the occasional question is not high-effort and is just as or more valid as a computer science term than as an alias for a python package.

But I'm not even sure which to request, if any. Or if that last option is just my impostor syndrome acting up.

6
  • 16
    NP complexity seems on-topic to me. A programmer can have expertise in approaching problems relating to NP-complexity. numpy users should type the three extra letters for their tag.
    – khelwood
    Commented Dec 18, 2020 at 11:48
  • 8
    @khelwood While I don't disagree, there may be some benefit in renaming [np] to [np-complexity], if it is causing confusion and/or mistagging. Commented Dec 18, 2020 at 12:16
  • 7
    np should not be a synonym of numpy even when NP questions were off-topic. NP is a common abbreviation of "nondeterministic polynomial" and widely used in computer science, whereas NP as a abbreviation of NumPy is only/mainly used in the Python community. So this (for most) unexpected link to NumPy could result in incorrect tagging. I would then rather suggest to rename the tag, like suggest in the question, and block the re-creation of an np tag to prevent further ambiguity.
    – Tom
    Commented Dec 18, 2020 at 12:36
  • 4
    The bulk of mistagging comes from np frequently being imported as import numpy as np. I support renaming np to np-complexity, but in the style of a burnination and rather getting rid of np entirely rather than renaming it precisely to prevent ambiguous use. np potentially has several uses that leads to a high risk of misuse. TL;DR: move polynomial questions to np-complexity, move numpy questions to the numpy tag, and burn the tag to prevent further ambiguous use Commented Dec 18, 2020 at 12:37
  • 1
    So option 2B: rename the np tag np-complexity and don't have a plain np tag at all.
    – khelwood
    Commented Dec 18, 2020 at 13:06
  • Another possible collision is for Notepad or Notepad++ (though I have never seen it - only N++, NP++, npp, and NPP). Commented Dec 18, 2020 at 18:00

1 Answer 1

3

Considering that the tag also exists, it does not make sense to have both. It is less often used however:

I think it would probably make more sense to use to avoid confusion, so a should be executed. I don't think a synonym request is appropriate, considering the current misuse.

should then not be used anymore.

2
  • 2
    I don't think NP-hard is the same as NP.
    – khelwood
    Commented Dec 22, 2020 at 23:59
  • @khelwood Indeed, but I don't think it makes sense to have both tags either. P and NP-complete are both part of NP, NP-complete is also part of NP-hard. All of them are part of complexity-theory (4228 questions). Not sure we need tags for each, and I think questions about one will most likely also be about the others.
    – Didier L
    Commented Dec 23, 2020 at 0:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .