summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/complexity/complexity.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Master/texmf-dist/doc/latex/complexity/complexity.tex')
-rw-r--r--Master/texmf-dist/doc/latex/complexity/complexity.tex556
1 files changed, 556 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/complexity/complexity.tex b/Master/texmf-dist/doc/latex/complexity/complexity.tex
new file mode 100644
index 00000000000..ceca44f586e
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/complexity/complexity.tex
@@ -0,0 +1,556 @@
+% complexity latex package documentation
+% Copyright 2005, by Chris Bourke <cbourke@cse.unl.edu>.
+% http://www.cse.unl.edu/~cbourke
+%
+% Please do not distribute altered versions of this document
+
+\documentclass{ltxdoc}
+
+\def\complexityversion{0.76}
+
+%\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\\
+% \href{mailto:cbourke@cse.unl.edu}{\texttt{cbourke@cse.unl.edu}}
+}
+\date{March 22nd, 2005}
+
+\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.
+
+\subsection{Why a \texttt{complexity} package?}
+
+A better question is why not? Complexity theory is a more recent,
+though mature area of Theoretical Computer Science. Each researcher
+seems to have his or her own preferences as to how to typeset
+Complexity Classes and has built up their own personal \LaTeX\
+commands file. This can be frustrating, to say the least, when it
+comes to collaborations or when one has to go through an entire
+series of files changing commands for compatibility or to get
+exactly the look they want (or what may be required). I find it
+amazing that a package hasn't been written \emph{already}! (Maybe
+there has been, but I've not found it).
+
+I thought the best solution would be to develop a single \LaTeX\
+package to handle all of this for us.
+
+\section{Installation}
+
+You should place the |complexity| directory and its files
+(|complexity.sty| and |mycomplexity.sty| as well the documentation
+files if you like) in a place that your \TeX\ distribution will be
+able to find them.
+
+If you use MiK\TeX\ then you should place it in your |localtexmf|
+directory, making sure to refresh your \TeX\ tree (MiK\TeX\ options
+wizard $\rightarrow$ General $\rightarrow$ File Names Database,
+Refresh Now).
+
+In a unix \TeX\ distribution, you may find it useful to use a local
+\LaTeX\ path (i.e. creating a directory
+|/usr/local/username/mylatexfolder/| and tell your \TeX\
+distribution where to find it. Depending on your distribution, you
+might declare an environmental variable (say
+in your |.cshrc| file) like %
+
+|setenv $TEXINPUTS = /usr/local/texdistro//:/usr/local/username/mylatexfolder//|%
+
+(note that the double slash will recursively search all
+subdirectories).
+
+\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.\footnote{Deciding which classes were most
+``common'' was purely based on my judgement, for better or worse. If
+I've not considered your favorite complexity class as ``common,'' I
+humbly apologize.}
+
+\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}
+
+Different researchers and different publications have their own
+preferences for how to typeset complexity classes. The beauty of
+the |complexity| package is that it not only defines a whole sleigh
+of complexity classes \emph{for you}, but it also allows you to
+change the font they are typeset in with a simple option call.
+
+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. This
+is not so important for classes such as $\P$ and $\NP$, but if you
+are referencing 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. To
+illustrate, consider the following:
+\begin{quote}
+There are deterministic classes such as $\PSPACE \hbox{\small
+\PSPACE}$\kern-.3em, nondeterministic classes such as $\NP
+\hbox{\small \NP}$\kern-.35em, and functional classes such as $\GapP
+\hbox{\small \GapP}$\kern-.35em. But I like them all.
+\end{quote} % Internal note: the negative kerning was added here
+ % for illustration only, the package typesets these classes
+ % with a correct amount of spacing when |small| is used!
+
+In the preceding pairs, the first was typeset in the document's
+default font size while the second was typeset 1pt smaller
+(internally, the |\small| command is used). The difference is
+subtle but when used in a long text, flows more naturally.
+
+To get the same effect using |complexity|, simply use the |small|
+option (i.e. |\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.
+
+It should be noted that this option only affects how classes are
+typeset in the display and in-line mathmodes. It has no effect in,
+say, 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.
+
+
+\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. A word of warning,
+however, if you use a command outside of mathmode, \TeX\ may not
+properly insert surrounding whitespace. Thus, its best to always
+use |complexity| commands inside mathmode. A complete list of
+commands for classes can be found in Section
+\ref{sec:CompleteListOfComplexityCommands}.
+
+\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.
+
+Additionally, it may be the case that other \LaTeX\ packages are
+loaded that already define (or redefine) some of the commands in the
+|complexity| package. If this is the case, please email me so that
+I can work something out for future updates. The quick solution is
+to simply comment out the definition of the conflicting command in
+|complexity.sty| and directly use |\ComplexityFont{}| to typeset
+your complexity class (see also Section \ref{sec:Customization} -
+Customization).
+
+\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{7cm}}
+Command & Result & Comment \\
+\hline\hline\\
+|\llog| & $\llog$ & Denotes logarithmic functions. Note that 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 (subsets of
+$\{0,1\}^*$). A complete list of predefined language commands can
+be found in Table \ref{table:LanguageCommands} below. 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, simply use the \LaTeX\
+command, |\newcommand| as follows. Say that we want to define the
+new complexity class, ``VCCC'' (``very complex complexity class'').
+We would use something like
+
+|\newcommand{\VCCC}{\ComplexityFont{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 wish to typeset the same class as
+$\ComplexityFont{pBPP}$. To do this, we use the \LaTeX\ command,
+|\renewcommand| as follows.
+
+|\renewcommand{\promiseBPP}{\ComplexityFont{pBPP}}|
+
+However, this only changes what the command does, not how we invoke
+it---we would still use |$\promiseBPP$|.
+
+As another 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. Say we want to change
+it so that it is typeset in the same font as the rest of the
+classes. We may use something like the following.
+
+\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 |\ComplexityFont|, however, you
+would use the command |\lang|. You can 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.
+
+|\newcommand{\GNI}{\lang{GNI}}|
+
+In our document, we would would use something like |$\GNI \in \AM$|.
+We can also redefine any predefined language commands using the
+|\renewcommand| 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.
+
+|\newcommand{\subexp}{\func{subexp}}|
+
+In our document, we could then use |$\subexp(n) = 2^{o(n)}$|.
+
+\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$. In an effort to resolve this question,
+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$. In an effort to resolve this question,
+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
+
+For an even more complicated example, check out the \LaTeX ed (PDF)
+version of the Complexity Zoo (\url{http://www.ComplexityZoo.com})
+available on my webpage (\url{http://www.cse.unl.edu/~cbourke})
+
+\section{Feedback}
+
+I'd very much appreciate feedback that would improve this package.
+Specifically, I'm looking for the following.
+
+\begin{itemize}
+
+ \item Inconsistencies in (or suggestions for better) notation
+
+ \item Errors, Typos, etc
+
+ \item Incompatibilities with other packages
+
+ \item Feature requests
+
+\end{itemize}
+
+You can email me at
+\href{mailto:cbourke@cse.unl.edu}{cbourke@cse.unl.edu}
+
+\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.
+
+\end{document}