% complexity latex package documentation % Copyright 2017, by Chris Bourke % 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}