2
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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}. $\endgroup$
    – Bruno
    Feb 21, 2014 at 7:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Feb 21, 2014 at 9:57
  • 5
    $\begingroup$ "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. $\endgroup$
    – Niel de Beaudrap
    Feb 21, 2014 at 11:51
  • 5
    $\begingroup$ Has anyone implemented a standard? — Yes. In fact, everyone has implemented their own standard. $\endgroup$
    – Jeffε
    Feb 21, 2014 at 13:03
  • 1
    $\begingroup$ @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... $\endgroup$
    – Sam Nead
    Feb 21, 2014 at 13:12

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ They are not posting them as answers probably because they don't think it is good question for cstheory. $\endgroup$
    – Kaveh
    Feb 21, 2014 at 17:14
  • $\begingroup$ @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. $\endgroup$
    – Sam Nead
    Feb 22, 2014 at 22:49
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Feb 22, 2014 at 23:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Feb 22, 2014 at 23:26
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – Sam Nead
    Feb 23, 2014 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.