Skip to main content
1 of 2
Daniel F
  • 14.3k
  • 14
  • 18

An [np]-hard question

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

Daniel F
  • 14.3k
  • 14
  • 18