summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/complexity/complexity.tex
blob: 97e4102e8c6e168d58341d52e2dd3f1860b0934f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
% complexity latex package documentation
% Copyright 2017, by Chris Bourke <cbourke@cse.unl.edu>
% http://chrisbourke.unl.edu
%
% Please do not distribute altered versions of this document

\documentclass{ltxdoc}

\def\complexityversion{0.81a}

%\usepackage{amsmath}
\usepackage[pdftex,a4paper,colorlinks,pdfpagemode=None]{hyperref}
\usepackage{longtable}
\usepackage{complexity}

\setlength{\parindent}{0pt} %
\setlength{\parskip}{.25cm} %

\begin{document}

\title{User's Guide for \texttt{complexity}: a \LaTeX\ package, Version \complexityversion}
\author{Chris Bourke}
\date{\today}

\maketitle

\tableofcontents

\section{Introduction}

\subsection{What is \texttt{complexity}?}

\texttt{complexity} is a \LaTeX\ package that typesets computational
complexity classes such as $\P$ (deterministic polynomial time) and
$\NP$ (nondeterministic polynomial time) as well as sets (languages)
such as $\SAT$ (satisfiability).  In all, over 350 commands are
defined for helping you to typeset Computational Complexity
constructs.

\section{Package Options}

The |complexity| package provides two general options---a
\emph{font} option (of which there are three classes) and a
\emph{mode} option. The font option specifies what font the
complexity classes (as well as functions and languages) are typeset
in while the mode option specifies \emph{how many} complexity
classes are defined.

One specifies these options in the usual manner.  When you use the
package, you can pass it the options you wish; for example, calling
the package with

|\usepackage[bold,full]{complexity}|

specifies that classes (and languages) should be typeset in bold and
that the full list of classes should be defined.  Invalid options
are ignored and only the last option (of each type) is used if
multiple, conflicting options are given.  The complete options are
described in the next two subsections.

\subsection{Mode Options}

The mode options specify to what extent the package declares
commands for complexity classes.  By default, \emph{every}
(supported) class command is defined.  Alternatively, you can limit
the number of commands the |complexity| package defines (and perhaps
limit conflicts with other packages or your own commands) by using
the |basic| option. This option defines only the most commonly used
complexity classes.

\begin{description}

  \item[|full|] (\emph{Default}) This option will load \emph{every} complexity class
  that the package has defined.  See Section
  \ref{sec:CompleteListOfComplexityCommands} for a complete list.

  \item[|basic|]  This option will only load the
  ``standard'' complexity classes so as to minimize the number of
  commands the package defines (i.e. standard classes like $\P$ and
  $\NP$ but not less well known classes like $\AWPP$ (Almost wide $\PP$).

\end{description}

\subsection{Font Options}

You can easily change the fonts for complexity classes using
a package option.  The |complexity| package defines three different
font entities: a font for complexity classes (|classfont|), a font
for languages (|langfont|), and a font for functions (|funcfont|).
By default, all of these fonts are typeset using the |mathsf| font.
You can change the font for all of them together or specify a font
for each individually.  To apply a single font to all three entities,
simply pass the font (by itself) as an option.  The supported font
options are as follows.

\begin{description}

  \item[|sanserif|]  (\emph{Default}) This typesets the classes in a
  |\mathsf| (sans serif) font.

  \item[|roman|]  This option typesets the classes in a |\mathrm| (roman)
  font.

  \item[|bold|]   This option typesets the classes in a |\mathbf|
  (roman, bold) font.

  \item[|typewriter|]   This option typesets the classes in a |\mathtt|
  (typewriter) font.

  \item[|italic|]   This option typesets the classes in a |\mathit|
  (math italic) font.

  \item[|caps|]   This option typesets the classes in a |\textsc|
  (small caps font) font.

  \item[|slant|]   This option typesets the classes in a |\textsl|
  (slanted font) font.

\end{description}

As an alternative, you can specify a different font for each of the
three entities.  To do this, you simply qualify the font with a
key-value pair: either |classfont|, |langfont|, or |funcfont|.  For
example, if we want our complexity classes to be typeset in |bold|,
our languages to be typeset in |roman| and our functions to be
typeset in |italic|, we would call the package using:

\begin{verbatim}
\usepackage[classfont=bold,
            langfont=roman,
            funcfont=italic]{complexity}
\end{verbatim}

Examples of how each of the fonts appears when typeset can be found
in Table \ref{table:Examples}.

\begin{table}[h]
  \centering
  \caption{An Example of each font}\label{table:Examples}
\begin{tabular}{lp{3cm}p{4cm}p{3.5cm}}
Font & |classfont| & |langfont| & |funcfont| \\
\hline %
\hline %
~\\
|sanserif| & $\mathsf{P} \subseteq \mathsf{NP}$, & $\CVP \leq_m \SAT$, & $\polylog \in O(\poly)$,\\
~ & $\PSPACE \subseteq \EXP$ & $\SAT \leq_T \MaxSAT$ & $\polylog \in \Omega(\llog)$ \\
~\\
|roman| & $\mathrm{P} \subseteq \mathrm{NP}$, & $\mathrm{CVP} \leq_m \mathrm{SAT}$, & $\mathrm{polylog} \in O(\mathrm{poly})$,\\
~ & $\mathrm{PSPACE} \subseteq \mathrm{EXP}$ & $\mathrm{SAT} \leq_T \mathrm{MaxSAT}$ & $\mathrm{polylog} \in \Omega(\mathrm{log})$ \\
~\\
|bold| & $\mathbf{P} \subseteq \mathbf{NP}$, & $\mathbf{CVP} \leq_m \mathbf{SAT}$, & $\mathbf{polylog} \in O(\mathbf{poly})$,\\
~ & $\mathbf{PSPACE} \subseteq \mathbf{EXP}$ & $\mathbf{SAT} \leq_T \mathbf{MaxSAT}$ & $\mathbf{polylog} \in \Omega(\mathbf{log})$ \\
~\\
|typewriter| & $\mathtt{P} \subseteq \mathtt{NP}$, & $\mathtt{CVP} \leq_m \mathtt{SAT}$, & $\mathtt{polylog} \in O(\mathtt{poly})$,\\
~ & $\mathtt{PSPACE} \subseteq \mathtt{EXP}$ & $\mathtt{SAT} \leq_T \mathtt{MaxSAT}$ & $\mathtt{polylog} \in \Omega(\mathtt{log})$ \\
~\\
|italic| & $\mathit{P} \subseteq \mathit{NP}$, & $\mathit{CVP} \leq_m \mathit{SAT}$, & $\mathit{polylog} \in O(\mathit{poly})$,\\
~ & $\mathit{PSPACE} \subseteq \mathit{EXP}$ & $\mathit{SAT} \leq_T \mathit{MaxSAT}$ & $\mathit{polylog} \in \Omega(\mathit{log})$ \\
~\\
|caps| & $\textsc{P} \subseteq \textsc{NP}$, & $\textsc{CVP} \leq_m \textsc{SAT}$, & $\textsc{polylog} \in O(\textsc{poly})$,\\
~ & $\textsc{PSPACE} \subseteq \textsc{EXP}$ & $\textsc{SAT} \leq_T \textsc{MaxSAT}$ & $\textsc{polylog} \in \Omega(\textsc{log})$ \\
~ & \multicolumn{2}{l}{Better example: $\textsc{promiseRP} \subseteq \textsc{promiseBPP}$}\\
~\\
|slant| & $\textsl{P} \subseteq \textsl{NP}$, & $\textsl{CVP} \leq_m \textsl{SAT}$, & $\textsl{polylog} \in O(\textsl{poly})$,\\
~ & $\textsl{PSPACE} \subseteq \textsl{EXP}$ & $\textsl{SAT} \leq_T \textsl{MaxSAT}$ & $\textsl{polylog} \in \Omega(\textsl{log})$ \\
~\\
\end{tabular}
\end{table}

\subsubsection{The \texttt{small} Option}

A special option is the |small| option and pertains only to how
complexity classes (|classfont|) are typeset.  Since classes are
typeset in uppercase letters, they tend to be more dominant.  If
you frequently typeset classes such as $\PSPACE$ or $\DTIME$ it can
interrupt the normal flow of text layouts. One solution to this is
to typeset classes 1pt smaller than the surrounding text.  This is
the approach taken in some texts (most notably, Papadimitriou's book
\emph{Computational Complexity}, 1994) and it works quite well.
The following samples illustrate the difference.  The first sample
uses the default font size while the second uses a font that is 1pt
smaller (internally, the |\small| command is used).  The difference is
subtle but when used in a long text, flows more naturally.

\begin{quote}
There are deterministic classes such as $\PSPACE$, nondeterministic
classes such as $\NP$, and functional classes such as $\GapP$. But
I like them all.
\end{quote}

\begin{quote}
There are deterministic classes such as $\hbox{\small\PSPACE}$,
nondeterministic classes such as $\hbox{\small \NP}$, and functional
classes such as $\hbox{\small \GapP}$. But I like them all.
\end{quote}

To get the same effect using |complexity|, use the |small|
option:

|\usepackage[small]{complexity}|

with any combination of the other options (it works for all
fonts, but some do not look as good as others; |typewriter|
for example looks bad with this option). Remember, however
that this option only affects how classes are typeset, not
languages.

This option only affects how classes are
typeset in the display and in-line mathmodes.  It has no effect in
a footnote or some special environment. Subscripts,
superscripts (as well as subsubscripts and supersuperscripts) are
not effected either.  \TeX\ is allowed to automatically change font
sizes for these cases.

\subsection{Overridden Commands}

Three commands in the |complexity| package override built-in \TeX\
commands.  Specifically, |\L| (which typesets the symbol
\defaultL), |\P| (typesetting \defaultP), and |\S| (which typesets the
symbol \defaultS) are all redefined for use in the package.  The
|complexity| package preserves these commands so that you may still
use them.  To use any of these symbols, use the commands
|\defaultL|, |\defaultP|, and |\defaultS| instead.

In some situations this redefinition is not desirable (if you need
these symbols but cannot use the |\default| versions).  You can
disable the overriding of these three commands using the option
|disableredefinitions|; for example:

|\usepackage[disableredefinitions]{complexity}|

Three alternatives are defined if you disable the overrides:
|\cL|, |\cP| and |\cS| that typeset the classes $\cL$, $\cP$
and $\cS$ respectively.


\section{Using the Package}

Each of the commands is defined using |\ensuremath| so that you
need not be in \LaTeX's mathmode to use them.  However, if you
use a command outside of mathmode, \TeX\ may not properly insert
surrounding whitespace.  It is recommended to always use |complexity|
commands inside mathmode.  A complete list of commands for classes
can be found in Section \ref{sec:CompleteListOfComplexityCommands}.

\subsection{Special Commands}

In addition to complexity classes, the |complexity| package also
conveniently defines several commands for commonly used functions
and languages.  In particular, |\co| (ex: $\co$) and |\parity| (an
alias for |\oplus|, typesetting $\oplus$) can be placed preceding a
class to refer to the complement or counting versions respectively.

\subsection{Function Commands}

|complexity| defines several general classes of functions such as
logarithms and polynomials. Table \ref{table:SpecialCommands} gives
a complete list of these functions.

\begin{table}[h]
\centering %
\caption{\texttt{func} Commands} %
\label{table:SpecialCommands}
\begin{tabular}{llp{8cm}}
Command &   Result      & Comment \\
\hline\hline
|\llog|     & $\llog$   & Denotes logarithmic functions.  The command %
                          is invoked with \emph{two} l's so as to not interfere
                          with the \LaTeX\ |\log| command.\\
|\poly|     & $\poly$   & Denotes polynomial functions \\
|\polylog|  & $\polylog$ & Denotes polylogarithmic functions \\

|\qpoly|    & $\qpoly$  & Denotes polynomial functions for quantum advice\\
|\qlog|     & $\qlog$   & Denotes logarithmic functions for quantum advice \\

|\MOD|      & $\MOD$    & Used for Modular classes/functions \\
|\Mod|      & $\Mod$    & Used for Modular classes/functions \\
\end{tabular}
\end{table}

\subsection{Language Commands}

|complexity| also defines commands to typeset languages.
A complete list of predefined language commands can
be found in Table \ref{table:LanguageCommands}.  The number of
commands is sparse; this was intentional.  How one refers to
languages is far less standard than how one refers to classes.  Some
people like to explicitly write \emph{every} word
($\lang{WeightedHamiltonianCycle}$, or $\lang{WEIGHTED~HAMILTONIAN~
CYCLE}$), while others have their own abbreviations.  Keeping the
number of languages |complexity| defines to a minimum allows for the
maximum flexibility.

\begin{table}[h]
\centering %
\caption{Special \texttt{complexity} Commands} %
\label{table:LanguageCommands}
\begin{tabular}{llp{7cm}}
Command &   Result      & Comment \\
\hline\hline\\
|\CVP|      & $\CVP$    & Used for the Circuit Value Problem (a $\P$-complete set) \\
|\SAT|      & $\SAT$    & Used for Satisfiability (an $\NP$-complete set)\\
|\MaxSAT|   & $\MaxSAT$ & Used for the Lexicographically maximum
satisfiability optimization problem (complete for $\OptP$) \\
\end{tabular}
\end{table}


\newpage
\subsection{Complete List of Class Commands}
\label{sec:CompleteListOfComplexityCommands}

A complete list (in alpha-numeric order according to the command
name) of complexity commands is given below.  The first item in each
row is the command itself.  The second is an example of how it is
typeset using the default |sanserif| font.  Finally, the third item
indicates which mode the command is defined in.

\begin{longtable}{lll}
%\caption{Complete Table of \texttt{complexity} Commands}
%\label{table:CompleteCommands}
\input{tableofclasses}
\end{longtable}


\section{Customization}
\label{sec:Customization}

The |complexity| package provides some 350 commands to typeset
complexity classes.  However, that should not mean that the commands
here are the \emph{only} ones you'll ever need. Expanding the list
of commands to suit your needs is very easy. Please note, however,
it is preferred that you not alter the base style file
(|complexity.sty|).  Instead, a file is provided for you to define
your commands in (|mycomplexity.sty|).

\subsection{Class Commands}
To define a new complexity class, you can use the |\newclass|
command which is similar (in fact is a macro for) the \LaTeX\
command, |\newcommand|.  The command takes two arguments: the
command that you will use and how the class will be typeset. For
example, say that we want to define the new complexity class,
``VCCC'' (``very complex complexity class''). We would use

|\newclass{\VCCC}{VCCC}|

Then, anytime we wanted to typeset our new class, we simply use
|$\VCCC$|.  Internally, |complexity| typesets everything using the
command |\ComplexityFont| which is setup at the invocation of the
package.

You also may have different preferences for typesetting the classes
that |complexity| already defines.  For instance, the class
$\promiseBPP$ (typeset using the command |\promiseBPP|) is typeset
with ``promise'' explicitly written. Preferring brevity over
clarity, you may wish to typeset the same class as
``$\ComplexityFont{pBPP}$''.  To do this, we use the |\renewclass|
as follows.

|\renewclass{\promiseBPP}{pBPP}|

However, this only changes what the command does, not how we invoke
it---we would still use |$\promiseBPP$|.

Consider a more complex example.  Say we want to change how the
class $\ModkL$ (typeset using the command |\ModkL|) is typeset. By
default, the subscript $k$ is typeset in regular mathmode.  We can
change it so that it is typeset in the same font as the rest of the
classes.  We will have to specify this using |\renewcommand| as
follows.

\begin{verbatim}
\renewcommand{\ModkL}{ %
  {
    \ComplexityFont{Mod}_{\ComplexityFont{k}}\ComplexityFont{L}
  }
}
\end{verbatim}

Note the use of ``extra'' brackets.  In your commands, more is
always better (or at least safer); since we are using subscripts and
superscripts, we want to ensure that if we use the |\ModkL| command
itself in a subscript or superscript (say as an oracle) are typeset
correctly.

\subsection{Language Commands}

You can define languages (to be typeset in the |langfont|) in a
similar manner.  Instead of using |\newclass|, however, you would
use the command |\newlang|.  You can also use |\lang| as a stand
alone command in your document (i.e. |$\lang{Matching} \in \P$|) or
you can define a command (using |\lang|) that can be reused
throughout your document. Again, we give an example.  Say we wanted
to typeset the language ``Graph Non-Isomorphism'' using the
abbreviation, ``GNI''. We could define something like the following.

|\newlang{\GNI}{GNI}|

In our document, we would would use something like |$\GNI \in \AM$|.
We can also redefine any predefined language commands using the
|\renewlang| command as before.

\subsection{Function Commands}

Again, the procedure for typesetting your own functions is the same
as for classes.  Here, however, you use the |\func| command.  You
can use it as a stand alone command (|$\func{lin}(n) \in \Theta(n)$|) %
or you can define a command that can be reused.  Say we wanted to
typeset a class of subexponential functions, say ``subexp''. We
could define something like the following.

|\newfunc{\subexp}{subexp}|

In our document, we could then use |$\subexp(n) = 2^{o(n)}$|. We can
redefine a function command using |\renewfunc|.

\section{Extended Example}

Here, we present an extended example using the package.  Consider
the following \TeX\ code.

\begin{verbatim}
\documentclass{article}
\usepackage{complexity}
\begin{document}
It follows immediately from the definitions of $\P$ and $\NP$ that
$$\P \subseteq \NP$$
but the million dollar question is whether or not $\P
\stackrel{?}{=} \NP$.  As a generalization to these classes,
Stockmeyer (1976) defined a \emph{polynomial} hierarchy using
oracles.

\textbf{Definition}[Stockmeyer 1976] \\
Let $\Delta_0\P = \Sigma_0\P = \Pi_0\P = \P$. Then for $i > 0$, let
 \begin{itemize}
   \item $\Delta_i\P = \P$ with a $\Sigma_{i-1}\P$ oracle.
   \item $\Sigma_i\P = \NP$ with $\Sigma_{i-1}\P$ oracle.
   \item $\Pi_i\P = \coNP$ with $\Sigma_{i-1}\P$ oracle.
 \end{itemize}
Then $\PH$ is the union of these classes for all nonnegative
constant $i$.

It has been shown that $\PH \subseteq \PSPACE$. Moreover, Toda
(1989) showed the following
\textbf{Theorem}
$$\PH \subseteq \P^\PP$$
and since since $\P^\PP = \P^{\#\P}$ it follows that
$$\PH \subseteq \P^{\#\P}$$

\end{document}
\end{verbatim}

\hrule

Would produce something like the following:

\hrule

It follows immediately from the definitions of $\P$ and $\NP$ that
$$\P \subseteq \NP$$
but the million dollar question is whether or not $\P
\stackrel{?}{=} \NP$.  As a generalization to these classes,
Stockmeyer (1976) defined a \emph{polynomial} hierarchy using
oracles.

\textbf{Definition}[Stockmeyer 1976] \\
Let $\Delta_0\P = \Sigma_0\P = \Pi_0\P = \P$. Then for $i > 0$, let
 \begin{itemize}
   \item $\Delta_i\P = \P$ with a $\Sigma_{i-1}\P$ oracle.
   \item $\Sigma_i\P = \NP$ with $\Sigma_{i-1}\P$ oracle.
   \item $\Pi_i\P = \coNP$ with $\Sigma_{i-1}\P$ oracle.
 \end{itemize}
Then $\PH$ is the union of these classes for all nonnegative
constant $i$.

It has been shown that $\PH \subseteq \PSPACE$. Moreover, Toda
(1989) showed the following.

\textbf{Theorem}
$$\PH \subseteq \P^\PP$$
and since since $\P^\PP = \P^{\#\P}$ it follows that
$$\PH \subseteq \P^{\#\P}$$

\hrule

\subsection{Acknowledgements}

I'd like to thank Till Tantau for several useful suggestions and
feature requests as well as some clever code segments for the
|small| option.  I'd also like to thank Enrico Gregorio for the
suggested fix to disable redefinitions.

\end{document}