diff options
Diffstat (limited to 'macros/latex/contrib/complexity/complexity.tex')
-rw-r--r-- | macros/latex/contrib/complexity/complexity.tex | 493 |
1 files changed, 493 insertions, 0 deletions
diff --git a/macros/latex/contrib/complexity/complexity.tex b/macros/latex/contrib/complexity/complexity.tex new file mode 100644 index 0000000000..97e4102e8c --- /dev/null +++ b/macros/latex/contrib/complexity/complexity.tex @@ -0,0 +1,493 @@ +% complexity latex package documentation +% Copyright 2017, by Chris Bourke <cbourke@cse.unl.edu> +% http://chrisbourke.unl.edu +% +% Please do not distribute altered versions of this document + +\documentclass{ltxdoc} + +\def\complexityversion{0.81a} + +%\usepackage{amsmath} +\usepackage[pdftex,a4paper,colorlinks,pdfpagemode=None]{hyperref} +\usepackage{longtable} +\usepackage{complexity} + +\setlength{\parindent}{0pt} % +\setlength{\parskip}{.25cm} % + +\begin{document} + +\title{User's Guide for \texttt{complexity}: a \LaTeX\ package, Version \complexityversion} +\author{Chris Bourke} +\date{\today} + +\maketitle + +\tableofcontents + +\section{Introduction} + +\subsection{What is \texttt{complexity}?} + +\texttt{complexity} is a \LaTeX\ package that typesets computational +complexity classes such as $\P$ (deterministic polynomial time) and +$\NP$ (nondeterministic polynomial time) as well as sets (languages) +such as $\SAT$ (satisfiability). In all, over 350 commands are +defined for helping you to typeset Computational Complexity +constructs. + +\section{Package Options} + +The |complexity| package provides two general options---a +\emph{font} option (of which there are three classes) and a +\emph{mode} option. The font option specifies what font the +complexity classes (as well as functions and languages) are typeset +in while the mode option specifies \emph{how many} complexity +classes are defined. + +One specifies these options in the usual manner. When you use the +package, you can pass it the options you wish; for example, calling +the package with + +|\usepackage[bold,full]{complexity}| + +specifies that classes (and languages) should be typeset in bold and +that the full list of classes should be defined. Invalid options +are ignored and only the last option (of each type) is used if +multiple, conflicting options are given. The complete options are +described in the next two subsections. + +\subsection{Mode Options} + +The mode options specify to what extent the package declares +commands for complexity classes. By default, \emph{every} +(supported) class command is defined. Alternatively, you can limit +the number of commands the |complexity| package defines (and perhaps +limit conflicts with other packages or your own commands) by using +the |basic| option. This option defines only the most commonly used +complexity classes. + +\begin{description} + + \item[|full|] (\emph{Default}) This option will load \emph{every} complexity class + that the package has defined. See Section + \ref{sec:CompleteListOfComplexityCommands} for a complete list. + + \item[|basic|] This option will only load the + ``standard'' complexity classes so as to minimize the number of + commands the package defines (i.e. standard classes like $\P$ and + $\NP$ but not less well known classes like $\AWPP$ (Almost wide $\PP$). + +\end{description} + +\subsection{Font Options} + +You can easily change the fonts for complexity classes using +a package option. The |complexity| package defines three different +font entities: a font for complexity classes (|classfont|), a font +for languages (|langfont|), and a font for functions (|funcfont|). +By default, all of these fonts are typeset using the |mathsf| font. +You can change the font for all of them together or specify a font +for each individually. To apply a single font to all three entities, +simply pass the font (by itself) as an option. The supported font +options are as follows. + +\begin{description} + + \item[|sanserif|] (\emph{Default}) This typesets the classes in a + |\mathsf| (sans serif) font. + + \item[|roman|] This option typesets the classes in a |\mathrm| (roman) + font. + + \item[|bold|] This option typesets the classes in a |\mathbf| + (roman, bold) font. + + \item[|typewriter|] This option typesets the classes in a |\mathtt| + (typewriter) font. + + \item[|italic|] This option typesets the classes in a |\mathit| + (math italic) font. + + \item[|caps|] This option typesets the classes in a |\textsc| + (small caps font) font. + + \item[|slant|] This option typesets the classes in a |\textsl| + (slanted font) font. + +\end{description} + +As an alternative, you can specify a different font for each of the +three entities. To do this, you simply qualify the font with a +key-value pair: either |classfont|, |langfont|, or |funcfont|. For +example, if we want our complexity classes to be typeset in |bold|, +our languages to be typeset in |roman| and our functions to be +typeset in |italic|, we would call the package using: + +\begin{verbatim} +\usepackage[classfont=bold, + langfont=roman, + funcfont=italic]{complexity} +\end{verbatim} + +Examples of how each of the fonts appears when typeset can be found +in Table \ref{table:Examples}. + +\begin{table}[h] + \centering + \caption{An Example of each font}\label{table:Examples} +\begin{tabular}{lp{3cm}p{4cm}p{3.5cm}} +Font & |classfont| & |langfont| & |funcfont| \\ +\hline % +\hline % +~\\ +|sanserif| & $\mathsf{P} \subseteq \mathsf{NP}$, & $\CVP \leq_m \SAT$, & $\polylog \in O(\poly)$,\\ +~ & $\PSPACE \subseteq \EXP$ & $\SAT \leq_T \MaxSAT$ & $\polylog \in \Omega(\llog)$ \\ +~\\ +|roman| & $\mathrm{P} \subseteq \mathrm{NP}$, & $\mathrm{CVP} \leq_m \mathrm{SAT}$, & $\mathrm{polylog} \in O(\mathrm{poly})$,\\ +~ & $\mathrm{PSPACE} \subseteq \mathrm{EXP}$ & $\mathrm{SAT} \leq_T \mathrm{MaxSAT}$ & $\mathrm{polylog} \in \Omega(\mathrm{log})$ \\ +~\\ +|bold| & $\mathbf{P} \subseteq \mathbf{NP}$, & $\mathbf{CVP} \leq_m \mathbf{SAT}$, & $\mathbf{polylog} \in O(\mathbf{poly})$,\\ +~ & $\mathbf{PSPACE} \subseteq \mathbf{EXP}$ & $\mathbf{SAT} \leq_T \mathbf{MaxSAT}$ & $\mathbf{polylog} \in \Omega(\mathbf{log})$ \\ +~\\ +|typewriter| & $\mathtt{P} \subseteq \mathtt{NP}$, & $\mathtt{CVP} \leq_m \mathtt{SAT}$, & $\mathtt{polylog} \in O(\mathtt{poly})$,\\ +~ & $\mathtt{PSPACE} \subseteq \mathtt{EXP}$ & $\mathtt{SAT} \leq_T \mathtt{MaxSAT}$ & $\mathtt{polylog} \in \Omega(\mathtt{log})$ \\ +~\\ +|italic| & $\mathit{P} \subseteq \mathit{NP}$, & $\mathit{CVP} \leq_m \mathit{SAT}$, & $\mathit{polylog} \in O(\mathit{poly})$,\\ +~ & $\mathit{PSPACE} \subseteq \mathit{EXP}$ & $\mathit{SAT} \leq_T \mathit{MaxSAT}$ & $\mathit{polylog} \in \Omega(\mathit{log})$ \\ +~\\ +|caps| & $\textsc{P} \subseteq \textsc{NP}$, & $\textsc{CVP} \leq_m \textsc{SAT}$, & $\textsc{polylog} \in O(\textsc{poly})$,\\ +~ & $\textsc{PSPACE} \subseteq \textsc{EXP}$ & $\textsc{SAT} \leq_T \textsc{MaxSAT}$ & $\textsc{polylog} \in \Omega(\textsc{log})$ \\ +~ & \multicolumn{2}{l}{Better example: $\textsc{promiseRP} \subseteq \textsc{promiseBPP}$}\\ +~\\ +|slant| & $\textsl{P} \subseteq \textsl{NP}$, & $\textsl{CVP} \leq_m \textsl{SAT}$, & $\textsl{polylog} \in O(\textsl{poly})$,\\ +~ & $\textsl{PSPACE} \subseteq \textsl{EXP}$ & $\textsl{SAT} \leq_T \textsl{MaxSAT}$ & $\textsl{polylog} \in \Omega(\textsl{log})$ \\ +~\\ +\end{tabular} +\end{table} + +\subsubsection{The \texttt{small} Option} + +A special option is the |small| option and pertains only to how +complexity classes (|classfont|) are typeset. Since classes are +typeset in uppercase letters, they tend to be more dominant. If +you frequently typeset classes such as $\PSPACE$ or $\DTIME$ it can +interrupt the normal flow of text layouts. One solution to this is +to typeset classes 1pt smaller than the surrounding text. This is +the approach taken in some texts (most notably, Papadimitriou's book +\emph{Computational Complexity}, 1994) and it works quite well. +The following samples illustrate the difference. The first sample +uses the default font size while the second uses a font that is 1pt +smaller (internally, the |\small| command is used). The difference is +subtle but when used in a long text, flows more naturally. + +\begin{quote} +There are deterministic classes such as $\PSPACE$, nondeterministic +classes such as $\NP$, and functional classes such as $\GapP$. But +I like them all. +\end{quote} + +\begin{quote} +There are deterministic classes such as $\hbox{\small\PSPACE}$, +nondeterministic classes such as $\hbox{\small \NP}$, and functional +classes such as $\hbox{\small \GapP}$. But I like them all. +\end{quote} + +To get the same effect using |complexity|, use the |small| +option: + +|\usepackage[small]{complexity}| + +with any combination of the other options (it works for all +fonts, but some do not look as good as others; |typewriter| +for example looks bad with this option). Remember, however +that this option only affects how classes are typeset, not +languages. + +This option only affects how classes are +typeset in the display and in-line mathmodes. It has no effect in +a footnote or some special environment. Subscripts, +superscripts (as well as subsubscripts and supersuperscripts) are +not effected either. \TeX\ is allowed to automatically change font +sizes for these cases. + +\subsection{Overridden Commands} + +Three commands in the |complexity| package override built-in \TeX\ +commands. Specifically, |\L| (which typesets the symbol +\defaultL), |\P| (typesetting \defaultP), and |\S| (which typesets the +symbol \defaultS) are all redefined for use in the package. The +|complexity| package preserves these commands so that you may still +use them. To use any of these symbols, use the commands +|\defaultL|, |\defaultP|, and |\defaultS| instead. + +In some situations this redefinition is not desirable (if you need +these symbols but cannot use the |\default| versions). You can +disable the overriding of these three commands using the option +|disableredefinitions|; for example: + +|\usepackage[disableredefinitions]{complexity}| + +Three alternatives are defined if you disable the overrides: +|\cL|, |\cP| and |\cS| that typeset the classes $\cL$, $\cP$ +and $\cS$ respectively. + + +\section{Using the Package} + +Each of the commands is defined using |\ensuremath| so that you +need not be in \LaTeX's mathmode to use them. However, if you +use a command outside of mathmode, \TeX\ may not properly insert +surrounding whitespace. It is recommended to always use |complexity| +commands inside mathmode. A complete list of commands for classes +can be found in Section \ref{sec:CompleteListOfComplexityCommands}. + +\subsection{Special Commands} + +In addition to complexity classes, the |complexity| package also +conveniently defines several commands for commonly used functions +and languages. In particular, |\co| (ex: $\co$) and |\parity| (an +alias for |\oplus|, typesetting $\oplus$) can be placed preceding a +class to refer to the complement or counting versions respectively. + +\subsection{Function Commands} + +|complexity| defines several general classes of functions such as +logarithms and polynomials. Table \ref{table:SpecialCommands} gives +a complete list of these functions. + +\begin{table}[h] +\centering % +\caption{\texttt{func} Commands} % +\label{table:SpecialCommands} +\begin{tabular}{llp{8cm}} +Command & Result & Comment \\ +\hline\hline +|\llog| & $\llog$ & Denotes logarithmic functions. The command % + is invoked with \emph{two} l's so as to not interfere + with the \LaTeX\ |\log| command.\\ +|\poly| & $\poly$ & Denotes polynomial functions \\ +|\polylog| & $\polylog$ & Denotes polylogarithmic functions \\ + +|\qpoly| & $\qpoly$ & Denotes polynomial functions for quantum advice\\ +|\qlog| & $\qlog$ & Denotes logarithmic functions for quantum advice \\ + +|\MOD| & $\MOD$ & Used for Modular classes/functions \\ +|\Mod| & $\Mod$ & Used for Modular classes/functions \\ +\end{tabular} +\end{table} + +\subsection{Language Commands} + +|complexity| also defines commands to typeset languages. +A complete list of predefined language commands can +be found in Table \ref{table:LanguageCommands}. The number of +commands is sparse; this was intentional. How one refers to +languages is far less standard than how one refers to classes. Some +people like to explicitly write \emph{every} word +($\lang{WeightedHamiltonianCycle}$, or $\lang{WEIGHTED~HAMILTONIAN~ +CYCLE}$), while others have their own abbreviations. Keeping the +number of languages |complexity| defines to a minimum allows for the +maximum flexibility. + +\begin{table}[h] +\centering % +\caption{Special \texttt{complexity} Commands} % +\label{table:LanguageCommands} +\begin{tabular}{llp{7cm}} +Command & Result & Comment \\ +\hline\hline\\ +|\CVP| & $\CVP$ & Used for the Circuit Value Problem (a $\P$-complete set) \\ +|\SAT| & $\SAT$ & Used for Satisfiability (an $\NP$-complete set)\\ +|\MaxSAT| & $\MaxSAT$ & Used for the Lexicographically maximum +satisfiability optimization problem (complete for $\OptP$) \\ +\end{tabular} +\end{table} + + +\newpage +\subsection{Complete List of Class Commands} +\label{sec:CompleteListOfComplexityCommands} + +A complete list (in alpha-numeric order according to the command +name) of complexity commands is given below. The first item in each +row is the command itself. The second is an example of how it is +typeset using the default |sanserif| font. Finally, the third item +indicates which mode the command is defined in. + +\begin{longtable}{lll} +%\caption{Complete Table of \texttt{complexity} Commands} +%\label{table:CompleteCommands} +\input{tableofclasses} +\end{longtable} + + +\section{Customization} +\label{sec:Customization} + +The |complexity| package provides some 350 commands to typeset +complexity classes. However, that should not mean that the commands +here are the \emph{only} ones you'll ever need. Expanding the list +of commands to suit your needs is very easy. Please note, however, +it is preferred that you not alter the base style file +(|complexity.sty|). Instead, a file is provided for you to define +your commands in (|mycomplexity.sty|). + +\subsection{Class Commands} +To define a new complexity class, you can use the |\newclass| +command which is similar (in fact is a macro for) the \LaTeX\ +command, |\newcommand|. The command takes two arguments: the +command that you will use and how the class will be typeset. For +example, say that we want to define the new complexity class, +``VCCC'' (``very complex complexity class''). We would use + +|\newclass{\VCCC}{VCCC}| + +Then, anytime we wanted to typeset our new class, we simply use +|$\VCCC$|. Internally, |complexity| typesets everything using the +command |\ComplexityFont| which is setup at the invocation of the +package. + +You also may have different preferences for typesetting the classes +that |complexity| already defines. For instance, the class +$\promiseBPP$ (typeset using the command |\promiseBPP|) is typeset +with ``promise'' explicitly written. Preferring brevity over +clarity, you may wish to typeset the same class as +``$\ComplexityFont{pBPP}$''. To do this, we use the |\renewclass| +as follows. + +|\renewclass{\promiseBPP}{pBPP}| + +However, this only changes what the command does, not how we invoke +it---we would still use |$\promiseBPP$|. + +Consider a more complex example. Say we want to change how the +class $\ModkL$ (typeset using the command |\ModkL|) is typeset. By +default, the subscript $k$ is typeset in regular mathmode. We can +change it so that it is typeset in the same font as the rest of the +classes. We will have to specify this using |\renewcommand| as +follows. + +\begin{verbatim} +\renewcommand{\ModkL}{ % + { + \ComplexityFont{Mod}_{\ComplexityFont{k}}\ComplexityFont{L} + } +} +\end{verbatim} + +Note the use of ``extra'' brackets. In your commands, more is +always better (or at least safer); since we are using subscripts and +superscripts, we want to ensure that if we use the |\ModkL| command +itself in a subscript or superscript (say as an oracle) are typeset +correctly. + +\subsection{Language Commands} + +You can define languages (to be typeset in the |langfont|) in a +similar manner. Instead of using |\newclass|, however, you would +use the command |\newlang|. You can also use |\lang| as a stand +alone command in your document (i.e. |$\lang{Matching} \in \P$|) or +you can define a command (using |\lang|) that can be reused +throughout your document. Again, we give an example. Say we wanted +to typeset the language ``Graph Non-Isomorphism'' using the +abbreviation, ``GNI''. We could define something like the following. + +|\newlang{\GNI}{GNI}| + +In our document, we would would use something like |$\GNI \in \AM$|. +We can also redefine any predefined language commands using the +|\renewlang| command as before. + +\subsection{Function Commands} + +Again, the procedure for typesetting your own functions is the same +as for classes. Here, however, you use the |\func| command. You +can use it as a stand alone command (|$\func{lin}(n) \in \Theta(n)$|) % +or you can define a command that can be reused. Say we wanted to +typeset a class of subexponential functions, say ``subexp''. We +could define something like the following. + +|\newfunc{\subexp}{subexp}| + +In our document, we could then use |$\subexp(n) = 2^{o(n)}$|. We can +redefine a function command using |\renewfunc|. + +\section{Extended Example} + +Here, we present an extended example using the package. Consider +the following \TeX\ code. + +\begin{verbatim} +\documentclass{article} +\usepackage{complexity} +\begin{document} +It follows immediately from the definitions of $\P$ and $\NP$ that +$$\P \subseteq \NP$$ +but the million dollar question is whether or not $\P +\stackrel{?}{=} \NP$. As a generalization to these classes, +Stockmeyer (1976) defined a \emph{polynomial} hierarchy using +oracles. + +\textbf{Definition}[Stockmeyer 1976] \\ +Let $\Delta_0\P = \Sigma_0\P = \Pi_0\P = \P$. Then for $i > 0$, let + \begin{itemize} + \item $\Delta_i\P = \P$ with a $\Sigma_{i-1}\P$ oracle. + \item $\Sigma_i\P = \NP$ with $\Sigma_{i-1}\P$ oracle. + \item $\Pi_i\P = \coNP$ with $\Sigma_{i-1}\P$ oracle. + \end{itemize} +Then $\PH$ is the union of these classes for all nonnegative +constant $i$. + +It has been shown that $\PH \subseteq \PSPACE$. Moreover, Toda +(1989) showed the following +\textbf{Theorem} +$$\PH \subseteq \P^\PP$$ +and since since $\P^\PP = \P^{\#\P}$ it follows that +$$\PH \subseteq \P^{\#\P}$$ + +\end{document} +\end{verbatim} + +\hrule + +Would produce something like the following: + +\hrule + +It follows immediately from the definitions of $\P$ and $\NP$ that +$$\P \subseteq \NP$$ +but the million dollar question is whether or not $\P +\stackrel{?}{=} \NP$. As a generalization to these classes, +Stockmeyer (1976) defined a \emph{polynomial} hierarchy using +oracles. + +\textbf{Definition}[Stockmeyer 1976] \\ +Let $\Delta_0\P = \Sigma_0\P = \Pi_0\P = \P$. Then for $i > 0$, let + \begin{itemize} + \item $\Delta_i\P = \P$ with a $\Sigma_{i-1}\P$ oracle. + \item $\Sigma_i\P = \NP$ with $\Sigma_{i-1}\P$ oracle. + \item $\Pi_i\P = \coNP$ with $\Sigma_{i-1}\P$ oracle. + \end{itemize} +Then $\PH$ is the union of these classes for all nonnegative +constant $i$. + +It has been shown that $\PH \subseteq \PSPACE$. Moreover, Toda +(1989) showed the following. + +\textbf{Theorem} +$$\PH \subseteq \P^\PP$$ +and since since $\P^\PP = \P^{\#\P}$ it follows that +$$\PH \subseteq \P^{\#\P}$$ + +\hrule + +\subsection{Acknowledgements} + +I'd like to thank Till Tantau for several useful suggestions and +feature requests as well as some clever code segments for the +|small| option. I'd also like to thank Enrico Gregorio for the +suggested fix to disable redefinitions. + +\end{document} |