<p><em>For some obscure reason everyone is answering in comments, so let me comment in an answer.</em> </p>

<p>While I am not aware of any standard macros for this, I'm partial to the G&amp;J format (which is basically the format you use in the question. Namely, </p>

<blockquote>
  <p><strong>PROBLEM NAME</strong>  <br />
  <strong>INSTANCE</strong>: description of instance<br />
  <strong>QUESTION</strong>: description of problem</p>
</blockquote>

CC BY-SA 3.0
2014-02-21T17:14:01.743Z
They are not posting them as answers probably because they don't think it is good question for cstheory.
Kaveh
CC BY-SA 3.0
2014-02-22T22:49:29.967Z
@Kaveh - what would be a more appropriate forum for this question?  Note that I've already asked at the TeX StackExchange site.  By the way, I'm willing to believe that there is no standard.  I'll probably wait a day or two, and then just accept this answer.
Sam Nead
CC BY-SA 3.0
2014-02-22T23:25:08.670Z
This is definitely  not a TeX.Se question: a version that would make sense there would be: "here's the desired format: how do I implement it in LaTeX?". Personally I don't see this question as inappropriate for here, but maybe a little fringe.
Suresh Venkat
CC BY-SA 3.0
2014-02-22T23:26:05.637Z
I think it would have been more suitable to remain on [tex.se], the same way asking for math related LaTeX package would be more suitable for there than MO. Anyway, if there was a frequently used package the users on [tex.se] would know. Asking for software which can be helpful for research can be on-topic here but it is on the boarder line of the scope. I personally don't think this is a good question for cstheory, writing such a package wouldn't take more than an hour probably, asking the question seems lazy to me.
Kaveh
CC BY-SA 3.0
2014-02-22T23:29:44.057Z
In fact I would guess that part of the reason there is no such package is probably because it is so simple that there is no need to write a package for it.
Kaveh
CC BY-SA 3.0
2014-02-22T23:33:29.483Z
I merely reinterpreted the question as "is there a community standard for how to describe decision problems".
Suresh Venkat
CC BY-SA 3.0
2014-02-23T00:04:24.653Z
The question is not obviously inappropriate for TeX.SE: they do entertain questions about typesetting standards for other fields (eg. chemistry). I assume that this question is very incidental — while we accept some soft questions, this isn't really about TCS but a special case of technical writing.
Niel de Beaudrap
CC BY-SA 3.0
2014-02-23T09:52:33.517Z
@Kaveh - I'm not asking anybody to write a new macro package: quite the reverse.  I'm asking for pointers to existing formatting.   I'm of the opinion that it is better to ask a stupid question than to quietly remain in the dark. :)
Sam Nead
CC BY-SA 3.0
2014-02-23T12:06:44.220Z
If that is what you want to ask then you should edit your question because right now that is not what you are asking. Just ask if there is a standard way to present decision problem and remove the part related to LaTeX.
Kaveh
CC BY-SA 3.0
2014-02-21T16:47:39.263Z
2014-02-21T16:47:39.263Z
Suresh Venkat
<blockquote>
  <p>Is there a standard macro package, or just standard set of macros, for
  formatting decision problems in LaTeX?</p>
</blockquote>

<p>A <em>decision problem</em> is presented via the data "problem name", "instance", and "question", with the latter always having a yes or no answer.  For example FACTOR has, as an instance, a pair of positive integers (n,p) and has, as its question, "Does n have a factor less that q and greater than one?".  Here is an attempt to format FACTOR in HTML.</p>

<p>FACTOR<br>
<code></code><em>Instance</em>: $(n,q) \in \mathbb N \times \mathbb N$ <br/>
<code></code><em>Question</em>: Does $n$ have a factor bigger than one and less than $q$?</p>

<p>In the interest of not reinventing the wheel, I asked google, and found some homegrown macros, each with their own spacing, choice of fonts, and layout.  Has anyone implemented a standard?  Say, a standard journal in complexity theory? </p>

<p>For quite old examples of formatting choices see Karp's classic paper <a href="http://www.win.tue.nl/~gwoegi/AC/karp-1971.pdf%E2%80%8E" rel="nofollow">Reducibility among combinatorial problems</a>, starting on page 89 (using the page numbers in the book, not in the pdf file).  The book <a href="http://www.scribd.com/doc/176854596/3-Computers-and-Intractability-A-Guide-to-the-Theory-of-NP-Completeness-Garey-Johnson" rel="nofollow">Computers and intractability</a> by Garey and Johnson also gives many decision problems - see page 25 of the linked text.  I've seen more recent texts where the problem name is in small caps, and the boiler-plate on the instance and question lines is in italics. </p>

<p>For a more recent example, I found a macro written for use by students in a <a href="http://courses.cs.vt.edu/cs3824/Fall2011/homework2.tex" rel="nofollow">cs class</a> - see lines 95 to 116.  </p>

<p>Finally - I tried asking over at the TeX Stack Exchange site, but didn't get any answers.  I've deleted the question there, and moved it over here. </p>

CC BY-SA 3.0
2014-02-21T07:41:05.810Z
I have never seen any such *standard* macro package. The main reason (to my mind) is that there is no standard way to present the decision problems. Authors use many different ways to present them, and it depends on their taste and the problems they consider. A last comment: An idea could be to use `amsthm` and to define a `\newtheorem{decision}`.
Bruno
CC BY-SA 3.0
2014-02-21T09:57:06.623Z
This seems off-topic. Sure, research-level theoretical computer scientists need this macro but the question isn't about research-level computer science. It's hardly difficult to write a macro to do this, e.g., [modifying the `list` environment](http://en.wikibooks.org/wiki/LaTeX/List_Structures). The fact that you couldn't get an answer on [tex.SE] SE or find one with Google suggests that there's no standard package.
David Richerby
CC BY-SA 3.0
2014-02-21T11:51:13.597Z
"Sure, research-level theoretical computer scientists need this macro" ... well, not really. Especially when different conferences and journals have different styles, using a fixed environment or macro seems counterproductive. What is important is not for you to format it in a fixed way, but in a *clear* way. For this reson you could ask about *best practises for presentation* of decision problems, but the macro becomes a matter of tactics, where you might use one way in your personal notes but may have to adapt according to the vicissitudes of your publication venue.
Niel de Beaudrap
CC BY-SA 3.0
2014-02-21T13:03:02.913Z
_Has anyone implemented a standard?_ — Yes.  In fact, everyone has implemented their own standard.
Jeffε
CC BY-SA 3.0
2014-02-21T13:12:06.607Z
@NieldeBeaudrap - I am certainly interested in best practices.  I am most interested in writing clearly! :)
Sam Nead
CC BY-SA 3.0
2014-02-21T13:12:26.670Z
@JeffE - I've spend time looking at your algorithms notes.  Your preference is to state problems in-line, with the problem name in small-caps, and then writing out the decision problem in an English sentence.  Papadimitriou does something similar, except he always writes two sentences, the first with the givens and the second with the question: "We are then asked..."  I somewhat prefer the format given in the OP, as it is easier to find when skimming a paper or book...
Sam Nead
CC BY-SA 3.0
2014-02-21T15:46:48.943Z
@SamNead: the best way to learn about best practises are to read papers and lecture notes, and see how clear their problem definitions are. Also: think of how to effectively present (a slightly more formal version of) what you would tell someone in twenty seconds in line for coffee at a conference.
Niel de Beaudrap
CC BY-SA 3.0
2014-02-22T22:53:59.923Z
@NieldeBeaudrap - "Especially when different conferences and journals have different styles".  At this point I'd be happy just to get pointers towards formatting that you find particularly clear.  Thanks.
Sam Nead
CC BY-SA 3.0
2014-02-22T23:43:50.567Z
@SamNead: `\paragraph{Problem.} Given X, Y, Z, determine whether L` (or equivalent) is a good start. Alternatively: you could write `\paragraph{Problem.} Given X, Y, Z, determine whether \begin{itemize} \item L, or \item not-L \end{itemize} [maybe: given that one of the two holds]` is reasonable. The specific way you implement this presentation is up for grabs, my suggested implementation is vaguely generic.
Niel de Beaudrap
CC BY-SA 3.0
2014-02-23T09:50:46.540Z
@NieldeBeaudrap - Ah, sorry - by pointer I meant "the titles of papers or books" containing examples that "you find particularly clear".  But you are suggesting an interesting variant - problems are written in-line, but in their own paragraph: sort of like a named theorem in mathematics.  This is a nice compromise between Jeff's version (inline) and G&J (list): so the problem will be easy to find, but won't interrupt the visual flow of the writing.  Hmm.
Sam Nead
<cc.complexity-theory>
Formatting decision problems in LaTeX
Sam Nead
# Formatting decision problems in LaTeX

(Asked by: username_0 on 2014-02-20)

> Is there a standard macro package, or just standard set of macros, for
> formatting decision problems in LaTeX?

A *decision problem* is presented via the data "problem name", "instance", and "question", with the latter always having a yes or no answer. For example FACTOR has, as an instance, a pair of positive integers (n,p) and has, as its question, "Does n have a factor less that q and greater than one?". Here is an attempt to format FACTOR in HTML.

FACTOR  
*Instance*: $(n,q) \in \mathbb N \times \mathbb N$

In the interest of not reinventing the wheel, I asked google, and found some homegrown macros, each with their own spacing, choice of fonts, and layout. Has anyone implemented a standard? Say, a standard journal in complexity theory?

For quite old examples of formatting choices see Karp's classic paper [Reducibility among combinatorial problems](http://www.win.tue.nl/~gwoegi/AC/karp-1971.pdf%E2%80%8E), starting on page 89 (using the page numbers in the book, not in the pdf file). The book [Computers and intractability](http://www.scribd.com/doc/176854596/3-Computers-and-Intractability-A-Guide-to-the-Theory-of-NP-Completeness-Garey-Johnson) by Garey and Johnson also gives many decision problems - see page 25 of the linked text. I've seen more recent texts where the problem name is in small caps, and the boiler-plate on the instance and question lines is in italics.

For a more recent example, I found a macro written for use by students in a [cs class](http://courses.cs.vt.edu/cs3824/Fall2011/homework2.tex) - see lines 95 to 116.

Finally - I tried asking over at the TeX Stack Exchange site, but didn't get any answers. I've deleted the question there, and moved it over here.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: I have never seen any such *standard* macro package. The main reason (to my mind) is that there is no standard way to present the decision problems. Authors use many different ways to present them, and it depends on their taste and the problems they consider. A last comment: An idea could be to use `amsthm` and to define a `\newtheorem{decision}`.  
> **username_2**: This seems off-topic. Sure, research-level theoretical computer scientists need this macro but the question isn't about research-level computer science. It's hardly difficult to write a macro to do this, e.g., [modifying the `list` environment](http://en.wikibooks.org/wiki/LaTeX/List_Structures). The fact that you couldn't get an answer on [tex.SE] SE or find one with Google suggests that there's no standard package.  
> **username_3**: "Sure, research-level theoretical computer scientists need this macro" ... well, not really. Especially when different conferences and journals have different styles, using a fixed environment or macro seems counterproductive. What is important is not for you to format it in a fixed way, but in a *clear* way. For this reson you could ask about *best practises for presentation* of decision problems, but the macro becomes a matter of tactics, where you might use one way in your personal notes but may have to adapt according to the vicissitudes of your publication venue.  
> **username_4**: _Has anyone implemented a standard?_ — Yes.  In fact, everyone has implemented their own standard.  
> **username_0**: @NieldeBeaudrap - I am certainly interested in best practices.  I am most interested in writing clearly! :)  
> **username_0**: @JeffE - I've spend time looking at your algorithms notes.  Your preference is to state problems in-line, with the problem name in small-caps, and then writing out the decision problem in an English sentence.  Papadimitriou does something similar, except he always writes two sentences, the first with the givens and the second with the question: "We are then asked..."  I somewhat prefer the format given in the OP, as it is easier to find when skimming a paper or book...  
> **username_3**: @SamNead: the best way to learn about best practises are to read papers and lecture notes, and see how clear their problem definitions are. Also: think of how to effectively present (a slightly more formal version of) what you would tell someone in twenty seconds in line for coffee at a conference.  
> **username_0**: @NieldeBeaudrap - "Especially when different conferences and journals have different styles".  At this point I'd be happy just to get pointers towards formatting that you find particularly clear.  Thanks.  
> **username_3**: @SamNead: `\paragraph{Problem.} Given X, Y, Z, determine whether L` (or equivalent) is a good start. Alternatively: you could write `\paragraph{Problem.} Given X, Y, Z, determine whether \begin{itemize} \item L, or \item not-L \end{itemize} [maybe: given that one of the two holds]` is reasonable. The specific way you implement this presentation is up for grabs, my suggested implementation is vaguely generic.  
> **username_0**: @NieldeBeaudrap - Ah, sorry - by pointer I meant "the titles of papers or books" containing examples that "you find particularly clear".  But you are suggesting an interesting variant - problems are written in-line, but in their own paragraph: sort of like a named theorem in mathematics.  This is a nice compromise between Jeff's version (inline) and G&J (list): so the problem will be easy to find, but won't interrupt the visual flow of the writing.  Hmm.  

---

## 1 answers

### Answer by username_5 on 2014-02-21. Score: 2 | Accepted answer

*For some obscure reason everyone is answering in comments, so let me comment in an answer.*

While I am not aware of any standard macros for this, I'm partial to the G&J format (which is basically the format you use in the question. Namely,

> **PROBLEM NAME**   
> **INSTANCE**: description of instance  
> **QUESTION**: description of problem

> **Comments:**
> **username_6**: They are not posting them as answers probably because they don't think it is good question for cstheory.  
> **username_0**: @username_6 - what would be a more appropriate forum for this question?  Note that I've already asked at the TeX StackExchange site.  By the way, I'm willing to believe that there is no standard.  I'll probably wait a day or two, and then just accept this answer.  
> **username_5**: This is definitely  not a TeX.Se question: a version that would make sense there would be: "here's the desired format: how do I implement it in LaTeX?". Personally I don't see this question as inappropriate for here, but maybe a little fringe.  
> **username_6**: I think it would have been more suitable to remain on [tex.se], the same way asking for math related LaTeX package would be more suitable for there than MO. Anyway, if there was a frequently used package the users on [tex.se] would know. Asking for software which can be helpful for research can be on-topic here but it is on the boarder line of the scope. I personally don't think this is a good question for cstheory, writing such a package wouldn't take more than an hour probably, asking the question seems lazy to me.  
> **username_6**: In fact I would guess that part of the reason there is no such package is probably because it is so simple that there is no need to write a package for it.  
> **username_5**: I merely reinterpreted the question as "is there a community standard for how to describe decision problems".  
> **username_3**: The question is not obviously inappropriate for TeX.SE: they do entertain questions about typesetting standards for other fields (eg. chemistry). I assume that this question is very incidental — while we accept some soft questions, this isn't really about TCS but a special case of technical writing.  
> **username_0**: @username_6 - I'm not asking anybody to write a new macro package: quite the reverse.  I'm asking for pointers to existing formatting.   I'm of the opinion that it is better to ask a stupid question than to quietly remain in the dark. :)  
> **username_6**: If that is what you want to ask then you should edit your question because right now that is not what you are asking. Just ask if there is a standard way to present decision problem and remove the part related to LaTeX.  

---

