0
$\begingroup$

I recently created a new tag: . I do believe that this tag is indeed needed because its lack does lead to a lot of somewhat erroneously or misleadingly tagged questions.

For example, a question that has been asked several times over the past decade is how to determine whether a system of linear equations and linear inequalities has a solution over the reals. This is a decision problem. This decision problem can be solved using, say, linear programming, which is a decision procedure. Usually, such questions have the tag . However, Fourier-Motzkin could have been used as an alternative decision procedure.

Why are questions on decision problems being tagged with the tags corresponding to decision procedures? Because this makes little sense to me, I took the liberty of creating .

Constructive criticism is most welcome. Thank you for the attention.

$\endgroup$
7
  • 1
    $\begingroup$ I suspect that most of the users asking questions about systems of linear inequalities are studying the simplex method and wouldn't know from Fourier-Motzkin, so linear-programming is a good tag. I guess decision-problems is OK, provided users don't confuse it with decideability in math logic. $\endgroup$
    – Gerry Myerson
    Feb 21, 2019 at 9:24
  • 2
    $\begingroup$ @Gerry: I believe that decision problems are related to decidability from mathematical logic. $\endgroup$
    – Asaf Karagila Mod
    Feb 21, 2019 at 11:08
  • 1
    $\begingroup$ @Asaf, sure – but if beginner questions on the simplex method get mixed in with questions on Godel's theorems then the tag will have limited usefulness. $\endgroup$
    – Gerry Myerson
    Feb 21, 2019 at 11:32
  • 6
    $\begingroup$ @Gerry: Yes, that is my main worry. Not to mention people asking questions like "Help me decide which university to go to"... $\endgroup$
    – Asaf Karagila Mod
    Feb 21, 2019 at 13:18
  • 3
    $\begingroup$ (By the way, thank you, Rodrigo, for taking this topic to meta. I appreciate it very much!) $\endgroup$
    – Asaf Karagila Mod
    Feb 21, 2019 at 13:19
  • 3
    $\begingroup$ Probably some improvements to the tag-info would be useful. (Ideally coming from somebody who knows the area for which the tag is intended.) Currently it says just: A decision problem is a question whose answer is either "yes" or "no". With this description, I would not be surprised if less experienced users used the tag for multiple-choice questions from any area of mathematics - which probably is not the intended use of the tag. (I guess that this is along the lines of Asaf's comment about deciding about choice of university.) $\endgroup$
    – Martin Sleziak
    Feb 22, 2019 at 5:43
  • 1
    $\begingroup$ I think that this might lead to a wider discussion - for which the space in comments under an answer in the long thread would probably not be sufficient. Which is why I reopened the thread. (Of course, I might be wrong - I can promise that I won't use dupehammer on the same question more than once.) $\endgroup$
    – Martin Sleziak
    Mar 25, 2019 at 10:44

1 Answer 1

Reset to default
3
$\begingroup$

Decision problems per se are ubiquitous in mathematics, so some care is needed to identify how such a tag would be useful in organizing searches of the Math.SE corpus.

Your lead paragraph asserts that the tag is needed because "its lack does lead to a lot of somewhat erroneously or misleadingly tagged questions." But the second paragraph doesn't support this claim with its example of using for whether "a system of linear equations and linear inequalities has a solution over the reals." That tag is neither erroneous or misleading for such problems.

The phrase "decision problems" is useful (and familiar) in the context of of algorithms. See also . If the proposed tag were intended to have a wider application, it might cause difficulties like we have with and the more technical "word problem in group theory", for which serves as something of a work around.

$\endgroup$
3
  • $\begingroup$ With the proposed tag, I can search for all (properly tagged) questions in which LP is used as a decision procedure. Why would I do that? For instance, to flag duplicates, and avoid having each new generation of MSE contributors answering the very same questions over and over again. $\endgroup$
    – Rodrigo de Azevedo
    Feb 22, 2019 at 20:58
  • 1
    $\begingroup$ @RodrigodeAzevedo: Can you give me an example of a Question where linear programming is not used as a decision procedure? Or an example of two linear programming Questions where you see duplication that needs the proposed tag to discover the duplication? $\endgroup$
    – hardmath
    Feb 22, 2019 at 21:18
  • $\begingroup$ If finding them were easy! Going through 100s of questions on LP to find a few examples is not productive. But Rome was not built in a day. Tagging can take its time. $\endgroup$
    – Rodrigo de Azevedo
    Feb 22, 2019 at 21:30

You must log in to answer this question.

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