summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/complexity/complexity.tex
diff options
context:
space:
mode:
Diffstat (limited to 'macros/latex/contrib/complexity/complexity.tex')
-rw-r--r--macros/latex/contrib/complexity/complexity.tex493
1 files changed, 493 insertions, 0 deletions
diff --git a/macros/latex/contrib/complexity/complexity.tex b/macros/latex/contrib/complexity/complexity.tex
new file mode 100644
index 0000000000..97e4102e8c
--- /dev/null
+++ b/macros/latex/contrib/complexity/complexity.tex
@@ -0,0 +1,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}