% 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}