summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/latex/complexity
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2006-01-09 00:49:07 +0000
committerKarl Berry <karl@freefriends.org>2006-01-09 00:49:07 +0000
commit007f67a693e4d031fd3d792df8e4d5f43e2cb2e7 (patch)
tree90d17e00e572ecb1e24764b6f29c80e098b08d29 /Master/texmf-dist/doc/latex/complexity
parent950209b26f70aa87ed07c54f82a95b6f03b7c3a0 (diff)
doc/latex
git-svn-id: svn://tug.org/texlive/trunk@84 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/doc/latex/complexity')
-rw-r--r--Master/texmf-dist/doc/latex/complexity/README11
-rw-r--r--Master/texmf-dist/doc/latex/complexity/complexity.pdfbin0 -> 204317 bytes
-rw-r--r--Master/texmf-dist/doc/latex/complexity/complexity.tex556
-rw-r--r--Master/texmf-dist/doc/latex/complexity/tableofclasses.tex685
4 files changed, 1252 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/complexity/README b/Master/texmf-dist/doc/latex/complexity/README
new file mode 100644
index 00000000000..049509392cb
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/complexity/README
@@ -0,0 +1,11 @@
+
+complexity - a LaTeX package that defines commands to typeset
+Computational Complexity Classes such as $\P$ and $\NP$ (as well
+as hundreds of others). It also offers several options including
+which font classes are typeset in and how many are defined (all
+of them or just the basic, most commonly used ones).
+
+Written by Chris Bourke <cbourke@cse.unl.edu>
+
+No dependencies other than the standard ifthen package.
+See complexity.pdf for full documentation
diff --git a/Master/texmf-dist/doc/latex/complexity/complexity.pdf b/Master/texmf-dist/doc/latex/complexity/complexity.pdf
new file mode 100644
index 00000000000..8c680b12d32
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/complexity/complexity.pdf
Binary files differ
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}
diff --git a/Master/texmf-dist/doc/latex/complexity/tableofclasses.tex b/Master/texmf-dist/doc/latex/complexity/tableofclasses.tex
new file mode 100644
index 00000000000..eb93e150521
--- /dev/null
+++ b/Master/texmf-dist/doc/latex/complexity/tableofclasses.tex
@@ -0,0 +1,685 @@
+|\AC| & $\AC$ & basic \\
+
+|\A| & $\A$ & full \\
+
+|\ACC| & $\ACC$ & basic \\
+
+|\AH| & $\AH$ & basic \\
+
+|\AL| & $\AL$ & basic \\
+
+|\AlgP| & $\AlgP$ & full \\
+
+|\AM| & $\AM$ & basic \\
+
+|\AMEXP| & $\AMEXP$ & basic \\
+
+|\Amp| & $\Amp$ & full \\
+
+|\AmpMP| & $\AmpMP$ & full \\
+
+|\AmpPBQP| & $\AmpPBQP$ & full \\
+
+|\AP| & $\AP$ & basic \\
+
+|\APP| & $\APP$ & full \\
+
+|\APX| & $\APX$ & full \\
+
+|\AUCSPACE| & $\AUCSPACE$ & full \\
+
+|\AuxPDA| & $\AuxPDA$ & full \\
+
+|\AVBPP| & $\AVBPP$ & full \\
+
+|\AvE| & $\AvE$ & full \\
+
+|\AvP| & $\AvP$ & full \\
+
+|\AW| & $\AW$ & full \\
+
+|\AWPP| & $\AWPP$ & full \\
+
+|\betaP| & $\betaP$ & full \\
+
+|\BH| & $\BH$ & basic \\
+
+|\BP| & $\BP$ & full \\
+
+|\BPE| & $\BPE$ & basic \\
+
+|\BPEE| & $\BPEE$ & basic \\
+
+|\BPHSPACE| & $\BPHSPACE$ & full \\
+
+|\BPL| & $\BPL$ & full \\
+
+|\BPP| & $\BPP$ & basic \\
+
+|\BPPOBDD| & $\BPPOBDD$ & full \\
+
+|\BPPpath| & $\BPPpath$ & full \\
+
+|\BPQP| & $\BPQP$ & full \\
+
+|\BPSPACE| & $\BPSPACE$ & basic \\
+
+|\BPTIME| & $\BPTIME$ & basic \\
+
+|\BQNC| & $\BQNC$ & full \\
+
+|\BQNP| & $\BQNP$ & full \\
+
+|\BQP| & $\BQP$ & basic \\
+
+|\BQPOBDD| & $\BQPOBDD$ & full \\
+
+|\BQTIME| & $\BQTIME$ & basic \\
+
+|\C| & $\C$ & basic \\
+
+|\cc| & $\cc$ & basic \\
+
+|\CeL| & $\CeL$ & basic \\
+
+|\CeP| & $\CeP$ & basic \\
+
+|\CFL| & $\CFL$ & basic \\
+
+|\CH| & $\CH$ & basic \\
+
+%|\Check| & $\Check$ & full \\
+
+|\CkP| & $\CkP$ & basic \\
+
+|\CLOG| & $\CLOG$ & full \\
+
+|\CNP| & $\CNP$ & full \\
+
+|\coAM| & $\coAM$ & basic \\
+
+|\coBPP| & $\coBPP$ & basic \\
+
+|\coCeP| & $\coCeP$ & basic \\
+
+|\cofrIP| & $\cofrIP$ & full \\
+
+|\Coh| & $\Coh$ & full \\
+
+|\coMA| & $\coMA$ & basic \\
+
+|\compIP| & $\compIP$ & full \\
+
+|\compNP| & $\compNP$ & full \\
+
+|\coNE| & $\coNE$ & basic \\
+
+|\coNEXP| & $\coNEXP$ & basic \\
+
+|\coNL| & $\coNL$ & basic \\
+
+|\coNP| & $\coNP$ & basic \\
+
+|\coNQP| & $\coNQP$ & basic \\
+
+|\coRE| & $\coRE$ & basic \\
+
+|\coRNC| & $\coRNC$ & basic \\
+
+|\coRP| & $\coRP$ & basic \\
+
+|\coSL| & $\coSL$ & basic \\
+
+|\coUCC| & $\coUCC$ & full \\
+
+|\coUP| & $\coUP$ & basic \\
+
+|\CP| & $\CP$ & full \\
+
+|\CSIZE| & $\CSIZE$ & basic \\
+
+|\CSL| & $\CSL$ & full \\
+
+|\CZK| & $\CZK$ & full \\
+
+|\D| & $\D$ & full \\
+
+|\DCFL| & $\DCFL$ & full \\
+
+|\DET| & $\DET$ & basic \\
+
+|\DiffAC| & $\DiffAC$ & full \\
+
+|\DisNP| & $\DisNP$ & full \\
+
+|\DistNP| & $\DistNP$ & full \\
+
+|\DP| & $\DP$ & full \\
+
+|\DQP| & $\DQP$ & full \\
+
+|\DSPACE| & $\DSPACE$ & basic \\
+
+|\DTIME| & $\DTIME$ & basic \\
+
+|\DTISP| & $\DTISP$ & basic \\
+
+|\Dyn| & $\Dyn$ & full \\
+
+|\DynFO| & $\DynFO$ & full \\
+
+|\E| & $\E$ & basic \\
+
+|\EE| & $\EE$ & basic \\
+
+|\EEE| & $\EEE$ & basic \\
+
+|\EESPACE| & $\EESPACE$ & basic \\
+
+|\EEXP| & $\EEXP$ & basic \\
+
+|\EH| & $\EH$ & basic \\
+
+|\EL| & $\EL$ & full \\
+
+|\ELEMENTARY| & $\ELEMENTARY$ & full \\
+
+|\ELkP| & $\ELkP$ & full \\
+
+|\EPTAS| & $\EPTAS$ & basic \\
+
+|\EQBP| & $\EQBP$ & full \\
+
+|\EQP| & $\EQP$ & full \\
+
+|\EQTIME| & $\EQTIME$ & full \\
+
+|\ESPACE| & $\ESPACE$ & basic \\
+
+|\ExistsBPP| & $\ExistsBPP$ & full \\
+
+|\ExistsNISZK| & $\ExistsNISZK$ & full \\
+
+|\EXP| & $\EXP$ & basic \\
+
+|\EXPSPACE| & $\EXPSPACE$ & basic \\
+
+|\FBQP| & $\FBQP$ & full \\
+
+|\Few| & $\Few$ & full \\
+
+|\FewP| & $\FewP$ & full \\
+
+|\FH| & $\FH$ & full \\
+
+|\FNL| & $\FNL$ & basic \\
+
+|\FNP| & $\FNP$ & basic \\
+
+|\FO| & $\FO$ & full \\
+
+|\FOLL| & $\FOLL$ & full \\
+
+|\FP| & $\FP$ & basic \\
+
+|\FPR| & $\FPR$ & full \\
+
+|\FPRAS| & $\FPRAS$ & basic \\
+
+|\FPT| & $\FPT$ & full \\
+
+|\FPTAS| & $\FPTAS$ & full \\
+
+|\FPTnu| & $\FPTnu$ & full \\
+
+|\FPTsu| & $\FPTsu$ & full \\
+
+|\FQMA| & $\FQMA$ & basic \\
+
+|\frIP| & $\frIP$ & full \\
+
+|\FTAPE| & $\FTAPE$ & full \\
+
+|\FTIME| & $\FTIME$ & full \\
+
+|\G| & $\G$ & full \\
+
+|\GA| & $\GA$ & basic \\
+
+|\GANSPACE| & $\GANSPACE$ & full \\
+
+|\Gap| & $\Gap$ & basic \\
+
+|\GapAC| & $\GapAC$ & basic \\
+
+|\GapL| & $\GapL$ & basic \\
+
+|\GapP| & $\GapP$ & basic \\
+
+|\GC| & $\GC$ & full \\
+
+|\GCSL| & $\GCSL$ & full \\
+
+|\GI| & $\GI$ & basic \\
+
+|\GPCD| & $\GPCD$ & full \\
+
+|\Heur| & $\Heur$ & basic \\
+
+|\HeurBPP| & $\HeurBPP$ & basic \\
+
+|\HeurBPTIME| & $\HeurBPTIME$ & basic \\
+
+|\HkP| & $\HkP$ & full \\
+
+|\HSPACE| & $\HSPACE$ & basic \\
+
+|\HVSZK| & $\HVSZK$ & full \\
+
+|\IC| & $\IC$ & full \\
+
+|\IP| & $\IP$ & basic \\
+
+|\IPP| & $\IPP$ & full \\
+
+|\K| & $\K$ & basic \\
+
+|\kBQBP| & $\kBQBP$ & full \\
+
+|\kBWBP| & $\kBWBP$ & full \\
+
+|\kEQBP| & $\kEQBP$ & full \\
+
+|\kPBP| & $\kPBP$ & full \\
+
+|\KT| & $\KT$ & basic \\
+
+|\L| & $\L$ & basic \\
+
+|\LIN| & $\LIN$ & basic \\
+
+|\LkP| & $\LkP$ & full \\
+
+|\LOGCFL| & $\LOGCFL$ & full \\
+
+|\LogFew| & $\LogFew$ & basic \\
+
+|\LogFewNL| & $\LogFewNL$ & basic \\
+
+|\LOGNP| & $\LOGNP$ & full \\
+
+|\LOGSNP| & $\LOGSNP$ & full \\
+
+|\LWPP| & $\LWPP$ & full \\
+
+|\M| & $\M$ & full \\
+
+|\MA| & $\MA$ & basic \\
+
+|\MAC| & $\MAC$ & basic \\
+
+|\MAE| & $\MAE$ & basic \\
+
+|\MAEXP| & $\MAEXP$ & basic \\
+
+|\mAL| & $\mAL$ & basic \\
+
+|\MaxNP| & $\MaxNP$ & basic \\
+
+|\MaxPB| & $\MaxPB$ & basic \\
+
+|\MaxSNP| & $\MaxSNP$ & basic \\
+
+|\mcoNL| & $\mcoNL$ & basic \\
+
+|\MinPB| & $\MinPB$ & basic \\
+
+|\MIP| & $\MIP$ & basic \\
+
+|\MkP| & $\MkP$ & full \\
+
+|\mL| & $\mL$ & basic \\
+
+|\mNC| & $\mNC$ & basic \\
+
+|\mNL| & $\mNL$ & basic \\
+
+|\mNP| & $\mNP$ & basic \\
+
+|\ModkL| & $\ModkL$ & basic \\
+
+|\ModkP| & $\ModkP$ & basic \\
+
+|\ModP| & $\ModP$ & basic \\
+
+|\ModZkL| & $\ModZkL$ & full \\
+
+|\mP| & $\mP$ & basic \\
+
+|\MP| & $\MP$ & basic \\
+
+|\MPC| & $\MPC$ & basic \\
+
+|\mTC| & $\mTC$ & basic \\
+
+|\NAuxPDA| & $\NAuxPDA$ & full \\
+
+|\NC| & $\NC$ & basic \\
+
+|\NE| & $\NE$ & basic \\
+
+|\NEE| & $\NEE$ & basic \\
+
+|\NEEE| & $\NEEE$ & basic \\
+
+|\NEEXP| & $\NEEXP$ & basic \\
+
+|\NEXP| & $\NEXP$ & basic \\
+
+|\NIPZK| & $\NIPZK$ & full \\
+
+|\NIQPZK| & $\NIQPZK$ & full \\
+
+|\NIQSZK| & $\NIQSZK$ & full \\
+
+|\NISZK| & $\NISZK$ & full \\
+
+|\NL| & $\NL$ & basic \\
+
+|\NLIN| & $\NLIN$ & basic \\
+
+|\NLOG| & $\NLOG$ & full \\
+
+|\NP| & $\NP$ & basic \\
+
+|\NPC| & $\NPC$ & basic \\
+
+|\NPI| & $\NPI$ & basic \\
+
+|\NPMV| & $\NPMV$ & full \\
+
+|\NPMVsel| & $\NPMVsel$ & full \\
+
+|\NPO| & $\NPO$ & full \\
+
+|\NPOPB| & $\NPOPB$ & full \\
+
+|\NPSPACE| & $\NPSPACE$ & basic \\
+
+|\NPSV| & $\NPSV$ & full \\
+
+|\NPSVsel| & $\NPSVsel$ & full \\
+
+|\NQP| & $\NQP$ & basic \\
+
+|\NSPACE| & $\NSPACE$ & basic \\
+
+|\NT| & $\NT$ & full \\
+
+|\NTIME| & $\NTIME$ & basic \\
+
+|\OBDD| & $\OBDD$ & full \\
+
+|\OCQ| & $\OCQ$ & full \\
+
+|\Opt| & $\Opt$ & basic \\
+
+|\OptP| & $\OptP$ & basic \\
+
+|\p| & $\p$ & basic \\
+
+|\P| & $\P$ & basic \\
+
+|\PAC| & $\PAC$ & basic \\
+
+|\PBP| & $\PBP$ & full \\
+
+|\PCD| & $\PCD$ & basic \\
+
+|\Pclose| & $\Pclose$ & full \\
+
+|\PCP| & $\PCP$ & basic \\
+
+|\PermUP| & $\PermUP$ & full \\
+
+|\PEXP| & $\PEXP$ & basic \\
+
+|\PF| & $\PF$ & full \\
+
+|\PFCHK| & $\PFCHK$ & full \\
+
+|\PH| & $\PH$ & basic \\
+
+|\PhP| & $\PhP$ & full \\
+
+|\PINC| & $\PINC$ & full \\
+
+|\PIO| & $\PIO$ & full \\
+
+|\PKC| & $\PKC$ & full \\
+
+|\PL| & $\PL$ & basic \\
+
+|\PLF| & $\PLF$ & full \\
+
+|\PLL| & $\PLL$ & full \\
+
+|\PLS| & $\PLS$ & full \\
+
+|\POBDD| & $\POBDD$ & full \\
+
+|\PODN| & $\PODN$ & full \\
+
+|\polyL| & $\polyL$ & full \\
+
+|\PostBQP| & $\PostBQP$ & full \\
+
+|\PP| & $\PP$ & basic \\
+
+|\PPA| & $\PPA$ & full \\
+
+|\PPAD| & $\PPAD$ & full \\
+
+|\PPADS| & $\PPADS$ & full \\
+
+|\Ppoly| & $\Ppoly$ & basic \\
+
+|\PPP| & $\PPP$ & full \\
+
+|\PPSPACE| & $\PPSPACE$ & basic \\
+
+|\PQUERY| & $\PQUERY$ & full \\
+
+|\PR| & $\PR$ & full \\
+
+|\PrHSPACE| & $\PrHSPACE$ & full \\
+
+|\Promise| & $\Promise$ & basic \\
+
+|\PromiseBPP| & $\PromiseBPP$ & basic \\
+
+|\PromiseBQP| & $\PromiseBQP$ & basic \\
+
+|\PromiseP| & $\PromiseP$ & basic \\
+
+|\PromiseRP| & $\PromiseRP$ & basic \\
+
+|\PrSPACE| & $\PrSPACE$ & basic \\
+
+|\PSel| & $\PSel$ & full \\
+
+|\PSK| & $\PSK$ & full \\
+
+|\PSPACE| & $\PSPACE$ & basic \\
+
+|\PT| & $\PT$ & basic \\
+
+|\PTAPE| & $\PTAPE$ & full \\
+
+|\PTAS| & $\PTAS$ & basic \\
+
+|\PTWK| & $\PTWK$ & basic \\
+
+|\PZK| & $\PZK$ & full \\
+
+|\QAC| & $\QAC$ & basic \\
+
+|\QACC| & $\QACC$ & basic \\
+
+|\QAM| & $\QAM$ & basic \\
+
+|\QCFL| & $\QCFL$ & basic \\
+
+|\QCMA| & $\QCMA$ & basic \\
+
+|\QH| & $\QH$ & basic \\
+
+|\QIP| & $\QIP$ & basic \\
+
+|\QMA| & $\QMA$ & basic \\
+
+|\QMAM| & $\QMAM$ & basic \\
+
+|\QMIP| & $\QMIP$ & basic \\
+
+|\QMIPle| & $\QMIPle$ & full \\
+
+|\QMIPne| & $\QMIPne$ & full \\
+
+|\QNC| & $\QNC$ & basic \\
+
+|\QP| & $\QP$ & basic \\
+
+|\QPLIN| & $\QPLIN$ & full \\
+
+|\Qpoly| & $\Qpoly$ & full \\
+
+|\QPSPACE| & $\QPSPACE$ & basic \\
+
+|\QSZK| & $\QSZK$ & full \\
+
+|\R| & $\R$ & basic \\
+
+|\RE| & $\RE$ & basic \\
+
+|\REG| & $\REG$ & basic \\
+
+|\RevSPACE| & $\RevSPACE$ & full \\
+
+|\RHL| & $\RHL$ & full \\
+
+|\RHSPACE| & $\RHSPACE$ & full \\
+
+|\RL| & $\RL$ & basic \\
+
+|\RNC| & $\RNC$ & basic \\
+
+|\RNP| & $\RNP$ & full \\
+
+|\RP| & $\RP$ & basic \\
+
+|\RPP| & $\RPP$ & full \\
+
+|\RSPACE| & $\RSPACE$ & basic \\
+
+|\S| & $\S$ & basic \\
+
+|\SAC| & $\SAC$ & basic \\
+
+|\SAPTIME| & $\SAPTIME$ & full \\
+
+|\SBP| & $\SBP$ & full \\
+
+|\SC| & $\SC$ & basic \\
+
+|\SE| & $\SE$ & basic \\
+
+|\SEH| & $\SEH$ & basic \\
+
+|\Sel| & $\Sel$ & full \\
+
+|\SelfNP| & $\SelfNP$ & full \\
+
+|\SF| & $\SF$ & full \\
+
+|\SIZE| & $\SIZE$ & basic \\
+
+|\SKC| & $\SKC$ & basic \\
+
+|\SL| & $\SL$ & basic \\
+
+|\SLICEWISEPSPACE| & $\SLICEWISEPSPACE$ & full \\
+
+|\SNP| & $\SNP$ & full \\
+
+|\SOE| & $\SOE$ & full \\
+
+|\SP| & $\SP$ & full \\
+
+|\SPACE| & $\SPACE$ & basic \\
+
+|\spanP| & $\spanP$ & full \\
+
+|\SPARSE| & $\SPARSE$ & basic \\
+
+|\SPL| & $\SPL$ & basic \\
+
+|\SPP| & $\SPP$ & basic \\
+
+|\SUBEXP| & $\SUBEXP$ & basic \\
+
+|\symP| & $\symP$ & full \\
+
+|\SZK| & $\SZK$ & basic \\
+
+|\TALLY| & $\TALLY$ & full \\
+
+|\TC| & $\TC$ & basic \\
+
+|\TFNP| & $\TFNP$ & full \\
+
+|\ThC| & $\ThC$ & full \\
+
+|\TreeBQP| & $\TreeBQP$ & full \\
+
+|\TREEREGULAR| & $\TREEREGULAR$ & full \\
+
+|\UAP| & $\UAP$ & full \\
+
+|\UCC| & $\UCC$ & full \\
+
+|\UE| & $\UE$ & full \\
+
+|\UL| & $\UL$ & full \\
+
+|\UP| & $\UP$ & basic \\
+
+|\US| & $\US$ & full \\
+
+|\VNC| & $\VNC$ & full \\
+
+|\VNP| & $\VNP$ & full \\
+
+|\VP| & $\VP$ & full \\
+
+|\VQP| & $\VQP$ & full \\
+
+|\W| & $\W$ & basic \\
+
+|\WAPP| & $\WAPP$ & full \\
+
+|\WPP| & $\WPP$ & full \\
+
+|\XORMIP| & $\XORMIP$ & full \\
+
+|\XP| & $\XP$ & full \\
+
+|\XPuniform| & $\XPuniform$ & full \\
+
+|\YACC| & $\YACC$ & full \\
+
+|\ZPE| & $\ZPE$ & basic \\
+
+|\ZPP| & $\ZPP$ & basic \\
+
+|\ZPTIME| & $\ZPTIME$ & basic \\