# 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}. – Bruno Feb 21 '14 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. – David Richerby Feb 21 '14 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. – Niel de Beaudrap Feb 21 '14 at 11:51
• Has anyone implemented a standard? — Yes. In fact, everyone has implemented their own standard. – Jeffε Feb 21 '14 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... – Sam Nead Feb 21 '14 at 13:12