# Formatting decision problems in LaTeX

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$
Question: Does $n$ have a factor bigger than one and less than $q$?

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, starting on page 89 (using the page numbers in the book, not in the pdf file). The book Computers and intractability 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 - 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.

• 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}. Feb 21, 2014 at 7:41
• 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. The fact that you couldn't get an answer on TeX - LaTeX SE or find one with Google suggests that there's no standard package. Feb 21, 2014 at 9:57
• "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. Feb 21, 2014 at 11:51
• Has anyone implemented a standard? — Yes. In fact, everyone has implemented their own standard. Feb 21, 2014 at 13:03
• @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... Feb 21, 2014 at 13:12

## 1 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

• They are not posting them as answers probably because they don't think it is good question for cstheory. Feb 21, 2014 at 17:14
• @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. Feb 22, 2014 at 22:49
• 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. Feb 22, 2014 at 23:25
• I think it would have been more suitable to remain on TeX - LaTeX, 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 - LaTeX 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. Feb 22, 2014 at 23:26
• @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. :) Feb 23, 2014 at 9:52