diff options
author | Karl Berry <karl@freefriends.org> | 2006-01-09 00:49:07 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2006-01-09 00:49:07 +0000 |
commit | 007f67a693e4d031fd3d792df8e4d5f43e2cb2e7 (patch) | |
tree | 90d17e00e572ecb1e24764b6f29c80e098b08d29 /Master/texmf-dist/doc/latex/complexity | |
parent | 950209b26f70aa87ed07c54f82a95b6f03b7c3a0 (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/README | 11 | ||||
-rw-r--r-- | Master/texmf-dist/doc/latex/complexity/complexity.pdf | bin | 0 -> 204317 bytes | |||
-rw-r--r-- | Master/texmf-dist/doc/latex/complexity/complexity.tex | 556 | ||||
-rw-r--r-- | Master/texmf-dist/doc/latex/complexity/tableofclasses.tex | 685 |
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 Binary files differnew file mode 100644 index 00000000000..8c680b12d32 --- /dev/null +++ b/Master/texmf-dist/doc/latex/complexity/complexity.pdf 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 \\ |