summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/complexity
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/complexity
Initial commit
Diffstat (limited to 'macros/latex/contrib/complexity')
-rw-r--r--macros/latex/contrib/complexity/README30
-rw-r--r--macros/latex/contrib/complexity/complexity.pdfbin0 -> 257609 bytes
-rw-r--r--macros/latex/contrib/complexity/complexity.sty757
-rw-r--r--macros/latex/contrib/complexity/complexity.tex493
-rw-r--r--macros/latex/contrib/complexity/mycomplexity.sty15
-rw-r--r--macros/latex/contrib/complexity/tableofclasses.tex685
6 files changed, 1980 insertions, 0 deletions
diff --git a/macros/latex/contrib/complexity/README b/macros/latex/contrib/complexity/README
new file mode 100644
index 0000000000..865ab97100
--- /dev/null
+++ b/macros/latex/contrib/complexity/README
@@ -0,0 +1,30 @@
+
+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
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% Copyright and license
+% =====================
+%
+% Copyright (C) 2017 Chris Bourke
+%
+% This file may be distributed and/or modified under the conditions of
+% the LaTeX Project Public License, either version 1.3c of this license
+% or (at your option) any later version. The latest version of this
+% license is in:
+%
+% http://www.latex-project.org/lppl.txt
+%
+% and version 1.3c or later is part of all distributions of LaTeX
+% version 2008/05/04 or later.
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
diff --git a/macros/latex/contrib/complexity/complexity.pdf b/macros/latex/contrib/complexity/complexity.pdf
new file mode 100644
index 0000000000..e83b01f00d
--- /dev/null
+++ b/macros/latex/contrib/complexity/complexity.pdf
Binary files differ
diff --git a/macros/latex/contrib/complexity/complexity.sty b/macros/latex/contrib/complexity/complexity.sty
new file mode 100644
index 0000000000..8acec3ac4d
--- /dev/null
+++ b/macros/latex/contrib/complexity/complexity.sty
@@ -0,0 +1,757 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% 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
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% Copyright and license
+% =====================
+%
+% Copyright (C) 2017 Chris Bourke
+%
+% This file may be distributed and/or modified under the conditions of
+% the LaTeX Project Public License, either version 1.3c of this license
+% or (at your option) any later version. The latest version of this
+% license is in:
+%
+% http://www.latex-project.org/lppl.txt
+%
+% and version 1.3c or later is part of all distributions of LaTeX
+% version 2008/05/04 or later.
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+% Changes made (.81 -> .81a, 2017/09/16)
+% -Updated copyright, added LPPL 1.3c
+% Changes made (.80 -> .81, 2017/09/15)
+% -Removed \typeout message
+% -Cleaned up comments
+% -Added package option (disableredefinitions) to disable redefinitions
+% of \L, \P, \S for authors that need the originals but cannot use the
+% replacements. For backwards compatibility, the they are still redefined
+% by default. Thanks to Enrico Gregorio for the fix.
+% Changes made (.76 -> .80)
+% -Added a cool message using \typeout!
+% -Added \newclass, \newlang, \newfunc commands
+% -Added \renewclass, \renewlang, \renewfunc
+% -Added \class that acts like \lang and \func
+% Changes made (.75 -> .76)
+% -Fixed a spacing bug that may cause extra spaces when not in math
+% mode. Thanks to Nicolas Markey
+% Changes made (.50 -> .75)
+% -Fixed a few misc. bugs
+% -Added negative kerning for \BPPpath, \FPTnu, \FPTsu, \QMIPle, \QMIPne, \XPuniform
+% -Added more {} brackets to all commands using sub/super scripts to ensure
+% proper behavior when they are used as super/subscripts themselves.
+% -Raised the hyphen and added kerning for all classes with hyphens adjoining capital
+% letters
+% -Made a few new internal commands (\complexity@possiblymakesmaller and
+% \complexity@fontcommand) to support a new option: small which typesets
+% classes in inline and display modes a point smaller than the default text
+% size. Special thanks to Till Tantau for the suggestions and code
+% -Defined separate commands \lang and \func for languages and function classes with
+% full options.
+% -Updated Documentation
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\NeedsTeXFormat{LaTeX2e} %
+\ProvidesPackage{complexity}[09/16/17 \space v0.81a]
+
+% Require Packages
+\RequirePackage{ifthen}
+
+% Declare internal commands
+\newcommand\complexity@possiblymakesmaller[1]{#1} % default: do nothing
+\newcommand\complexity@fontcommand{\mathsf} % default: do noting
+\newcommand{\ComplexityFont}[1]{%
+{\ensuremath{\complexity@possiblymakesmaller{\complexity@fontcommand{#1}}}}%extra {} makes everyone happy.
+}
+
+\newcommand{\lang}[1]{{\ensuremath{\mathsf{#1}}}}
+\newcommand{\func}[1]{{\ensuremath{\mathsf{#1}}}}
+\newcommand{\class}[1]{\ComplexityFont{#1}}
+
+\newcommand{\newclass}[2]{\newcommand{#1}{\ComplexityFont{#2}}}
+\newcommand{\newlang}[2]{\newcommand{#1}{\lang{#2}}}
+\newcommand{\newfunc}[2]{\newcommand{#1}{\func{#2}}}
+
+\newcommand{\renewclass}[2]{\renewcommand{#1}{\ComplexityFont{#2}}}
+\newcommand{\renewlang}[2]{\renewcommand{#1}{\lang{#2}}}
+\newcommand{\renewfunc}[2]{\renewcommand{#1}{\func{#2}}}
+
+\newboolean{complexity@fullmode} %
+\setboolean{complexity@fullmode}{true}
+\DeclareOption{full}{%
+ \setboolean{complexity@fullmode}{true}%
+} %
+\DeclareOption{basic}{%
+ \setboolean{complexity@fullmode}{false}%
+} %
+
+\newif\ifcomplexity@noredef
+\DeclareOption{disableredefinitions}{\complexity@noredeftrue}
+
+\DeclareOption{sanserif}{
+ \renewcommand{\complexity@fontcommand}{\mathsf}
+ \renewcommand{\lang}[1]{{\ensuremath{\mathsf{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\mathsf{#1}}}}
+}
+
+\DeclareOption{roman}{
+ \renewcommand{\complexity@fontcommand}{\mathrm}
+ \renewcommand{\lang}[1]{{\ensuremath{\mathrm{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\mathrm{#1}}}}
+}
+
+\DeclareOption{bold}{
+ \renewcommand{\complexity@fontcommand}{\mathbf}
+ \renewcommand{\lang}[1]{{\ensuremath{\mathbf{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\mathbf{#1}}}}
+}
+
+\DeclareOption{typewriter}{
+ \renewcommand{\complexity@fontcommand}{\mathtt}
+ \renewcommand{\lang}[1]{{\ensuremath{\mathtt{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\mathtt{#1}}}}
+}
+
+\DeclareOption{italic}{
+ \renewcommand{\complexity@fontcommand}{\mathit}
+ \renewcommand{\lang}[1]{{\ensuremath{\mathit{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\mathit{#1}}}}
+}
+
+\DeclareOption{caps}{
+ \renewcommand{\complexity@fontcommand}{\textsc}
+ \renewcommand{\lang}[1]{{\ensuremath{\textsc{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\textsc{#1}}}}
+}
+
+\DeclareOption{slant}{
+ \renewcommand{\complexity@fontcommand}{\textsl}
+ \renewcommand{\lang}[1]{{\ensuremath{\textsl{#1}}}}
+ \renewcommand{\func}[1]{{\ensuremath{\textsl{#1}}}}
+}
+
+% Independent classfonts:
+\DeclareOption{classfont=sanserif}{
+ \renewcommand{\complexity@fontcommand}{\mathsf}
+}
+\DeclareOption{classfont=roman}{
+ \renewcommand{\complexity@fontcommand}{\mathrm}
+}
+\DeclareOption{classfont=bold}{
+ \renewcommand{\complexity@fontcommand}{\mathbf}
+}
+\DeclareOption{classfont=typewriter}{
+ \renewcommand{\complexity@fontcommand}{\mathtt}
+}
+\DeclareOption{classfont=italic}{
+ \renewcommand{\complexity@fontcommand}{\mathit}
+}
+\DeclareOption{classfont=caps}{
+ \renewcommand{\complexity@fontcommand}{\textsc}
+}
+\DeclareOption{classfont=slant}{
+ \renewcommand{\complexity@fontcommand}{\textsl}
+}
+
+% Independent langfonts:
+\DeclareOption{langfont=sanserif}{
+ \renewcommand{\lang}[1]{{\ensuremath{\mathsf{#1}}}}
+}
+\DeclareOption{langfont=roman}{
+ \renewcommand{\lang}[1]{{\ensuremath{\mathrm{#1}}}}
+}
+\DeclareOption{langfont=bold}{
+ \renewcommand{\lang}[1]{{\ensuremath{\mathbf{#1}}}}
+}
+\DeclareOption{langfont=typewriter}{
+ \renewcommand{\lang}[1]{{\ensuremath{\mathtt{#1}}}}
+}
+\DeclareOption{langfont=italic}{
+ \renewcommand{\lang}[1]{{\ensuremath{\mathit{#1}}}}
+}
+\DeclareOption{langfont=caps}{
+ \renewcommand{\lang}[1]{{\ensuremath{\textsc{#1}}}}
+}
+\DeclareOption{langfont=slant}{
+ \renewcommand{\lang}[1]{{\ensuremath{\textsl{#1}}}}
+}
+
+% Independent funcfonts:
+\DeclareOption{funcfont=sanserif}{
+ \renewcommand{\func}[1]{{\ensuremath{\mathsf{#1}}}}
+}
+\DeclareOption{funcfont=roman}{
+ \renewcommand{\func}[1]{{\ensuremath{\mathrm{#1}}}}
+}
+\DeclareOption{funcfont=bold}{
+ \renewcommand{\func}[1]{{\ensuremath{\mathbf{#1}}}}
+}
+\DeclareOption{funcfont=typewriter}{
+ \renewcommand{\func}[1]{{\ensuremath{\mathtt{#1}}}}
+}
+\DeclareOption{funcfont=italic}{
+ \renewcommand{\func}[1]{{\ensuremath{\mathit{#1}}}}
+}
+\DeclareOption{funcfont=caps}{
+ \renewcommand{\func}[1]{{\ensuremath{\textsc{#1}}}}
+}
+\DeclareOption{funcfont=slant}{
+ \renewcommand{\func}[1]{{\ensuremath{\textsl{#1}}}}
+}
+
+% Till Tantau's Code for the small option:
+\DeclareOption{small}{
+
+\newcommand\complexity@reducesize{%
+ \ifx\@currsize\normalsize%
+ \small%
+ \else\ifx\@currsize\small%
+ \footnotesize%
+ \else\ifx\@currsize\large%
+ \normalsize%
+ \fi\fi\fi%
+}
+
+\renewcommand\complexity@possiblymakesmaller[1]{%
+ \mathchoice%
+ {\hbox{\complexity@reducesize$#1$}}% display
+ {\hbox{\complexity@reducesize$#1$}}% normal
+ {#1}%subscript
+ {#1}%subsubscript (I think)
+}
+
+}
+
+
+\DeclareOption*{
+\PackageWarning{complexity}{Unknown option `\CurrentOption'. Using default `sanserif', and `full'} %
+\renewcommand{\ComplexityFont}[1]{{\ensuremath{\mathsf{#1}}}}
+\renewcommand{\lang}[1]{{\ensuremath{\mathsf{#1}}}}
+\setboolean{complexity@fullmode}{true}
+}
+
+\ProcessOptions
+
+% Define some internal commands
+% such as a standard kerning value for several commands
+\newcommand{\complexity@kern}{{\kern-.10em}}
+\newcommand{\complexity@hyphen}{ %
+\lower-.12em\hbox{\textrm{-}} %
+}
+
+\newcommand{\complexity@hyphenleft}{\kern-.075em\textrm{-}}
+\newcommand{\complexity@hyphenright}{\textrm{-}\kern-.05em}
+
+% Define some useful commands to append to other classes
+
+\newcommand{\co}[1]{\ComplexityFont{co}#1}
+\newcommand{\parity}{\oplus}
+
+% Define some general functions
+\newcommand{\llog}{\func{log}}
+\newcommand{\poly}{\func{poly}}
+\newcommand{\polylog}{\func{polylog}}
+\newcommand{\qpoly}{\func{qpoly}}
+\newcommand{\qlog}{\func{qlog}}
+\newcommand{\MOD}{\func{MOD}}
+\newcommand{\Mod}{\func{Mod}}
+
+% Define Common Sets/Languages
+\newcommand{\CVP}{\lang{CVP}}
+\newcommand{\SAT}{\lang{SAT}}
+\newcommand{\MaxSAT}{\lang{MaxSAT}}
+
+
+% Alternatives for \L, \P, \S if disabled
+\newcommand{\cL}{\ComplexityFont{L}}
+\newcommand{\cP}{\ComplexityFont{P}}
+\newcommand{\cS}{\ComplexityFont{S}}
+
+% We redefine 3 commands, but preserve them for usage
+\let\defaultL\L % for back compatibility
+\let\defaultP\P % for back compatibility
+\let\defaultS\S % for back compatibility
+% Only redefine if not disabled
+\ifcomplexity@noredef\else
+\renewcommand{\L}{\ComplexityFont{L}}
+\renewcommand{\P}{\ComplexityFont{P}}
+\renewcommand{\S}{\ComplexityFont{S}}
+\fi
+
+
+% Major Classes listed in Alphabetical order
+
+%%%%%%% Standard Classes
+
+% A
+\newcommand{\AC}{\ComplexityFont{AC}}
+\newcommand{\ACC}{\ComplexityFont{ACC}}
+\newcommand{\AH}{\ComplexityFont{AH}}
+\newcommand{\AL}{\ComplexityFont{AL}}
+\newcommand{\coAM}{\ComplexityFont{coAM}}
+\newcommand{\AM}{\ComplexityFont{AM}}
+\newcommand{\AMEXP}{\ComplexityFont{AM\complexity@hyphen EXP}}
+\newcommand{\AP}{\ComplexityFont{AP}}
+
+% B
+\newcommand{\BH}{\ComplexityFont{BH}}
+\newcommand{\BPE}{\ComplexityFont{BPE}}
+\newcommand{\BPEE}{\ComplexityFont{BPEE}}
+\newcommand{\BPP}{\ComplexityFont{BPP}}
+\newcommand{\coBPP}{\ComplexityFont{coBPP}}
+\newcommand{\BPSPACE}{\ComplexityFont{BPSPACE}}
+\newcommand{\BPTIME}{\ComplexityFont{BPTIME}}
+\newcommand{\BQP}{\ComplexityFont{BQP}}
+\newcommand{\BQTIME}{\ComplexityFont{BQTIME}}
+
+% C
+\newcommand{\cc}{\ComplexityFont{cc}}
+\newcommand{\C}{\ComplexityFont{C}} %This isn't a class, but used for \C_{=}\AnotherClass
+\newcommand{\CeL}{\ComplexityFont{C}_{=}\ComplexityFont{L}} %C_=L
+\newcommand{\CeP}{\ComplexityFont{C}_{=}\ComplexityFont{P}} %C_=P
+\newcommand{\coCeP}{\ComplexityFont{coC}_{=}\ComplexityFont{P}} %C_=P
+\newcommand{\CFL}{\ComplexityFont{CFL}}
+\newcommand{\CH}{\ComplexityFont{CH}}
+\newcommand{\CkP}{\ComplexityFont{C}_{\ComplexityFont{k}}\ComplexityFont{P}} %C_kP
+\newcommand{\CSIZE}{\ComplexityFont{CSIZE}}
+
+% D
+\newcommand{\DET}{\ComplexityFont{DET}}
+\newcommand{\DSPACE}{\ComplexityFont{DSPACE}}
+\newcommand{\DTIME}{\ComplexityFont{DTIME}}
+\newcommand{\DTISP}{\ComplexityFont{DTISP}}
+
+% E
+\newcommand{\E}{\ComplexityFont{E}}
+\newcommand{\EE}{\ComplexityFont{EE}}
+\newcommand{\EESPACE}{\ComplexityFont{EESPACE}}
+\newcommand{\EEXP}{\ComplexityFont{EEXP}}
+\newcommand{\EH}{\ComplexityFont{EH}}
+\newcommand{\EEE}{\ComplexityFont{EEE}}
+\newcommand{\EPTAS}{\ComplexityFont{EPTAS}}
+\newcommand{\ESPACE}{\ComplexityFont{ESPACE}}
+\newcommand{\EXP}{\ComplexityFont{EXP}}
+\newcommand{\EXPSPACE}{\ComplexityFont{EXPSPACE}}
+
+% F
+\newcommand{\FNL}{\ComplexityFont{FNL}}
+\newcommand{\FNP}{\ComplexityFont{FNP}}
+\newcommand{\FP}{\ComplexityFont{FP}}
+\newcommand{\FPRAS}{\ComplexityFont{FPRAS}}
+\newcommand{\FQMA}{\ComplexityFont{FQMA}}
+
+% G
+\newcommand{\GA}{\ComplexityFont{GA}}
+\newcommand{\Gap}{\ComplexityFont{Gap}}
+\newcommand{\GapAC}{\ComplexityFont{GapAC}}
+\newcommand{\GapL}{\ComplexityFont{GapL}}
+\newcommand{\GapP}{\ComplexityFont{GapP}}
+\newcommand{\GI}{\ComplexityFont{GI}}
+
+% H
+\newcommand{\Heur}{\ComplexityFont{Heur}}
+\newcommand{\HSPACE}{\ComplexityFont{HSPACE}}
+\newcommand{\HeurBPP}{\ComplexityFont{HeurBPP}}
+\newcommand{\HeurBPTIME}{\ComplexityFont{HeurBPTIME}}
+
+% I
+\newcommand{\IP}{\ComplexityFont{IP}}
+
+% J
+
+% K
+\newcommand{\K}{\ComplexityFont{K}}
+\newcommand{\KT}{\ComplexityFont{KT}}
+
+% L
+\newcommand{\LIN}{\ComplexityFont{LIN}}
+\newcommand{\LogFew}{\ComplexityFont{LogFew}}
+\newcommand{\LogFewNL}{\ComplexityFont{LogFewNL}}
+
+% M
+\newcommand{\MA}{\ComplexityFont{MA}}
+\newcommand{\coMA}{\ComplexityFont{coMA}}
+\newcommand{\MAC}{\ComplexityFont{MAC}}
+\newcommand{\MAE}{\ComplexityFont{MA\complexity@hyphen E}}
+\newcommand{\MAEXP}{\ComplexityFont{MA\complexity@hyphen EXP}}
+\newcommand{\mAL}{\ComplexityFont{mAL}}
+\newcommand{\MaxNP}{\ComplexityFont{MaxNP}}
+\newcommand{\MaxPB}{\ComplexityFont{MaxPB}}
+\newcommand{\MaxSNP}{\ComplexityFont{MaxSNP}}
+\newcommand{\MinPB}{\ComplexityFont{MinPB}}
+\newcommand{\MIP}{\ComplexityFont{MIP}}
+\newcommand{\mL}{\ComplexityFont{mL}}
+\newcommand{\mNC}{\ComplexityFont{mNC}}
+\newcommand{\mcoNL}{\ComplexityFont{comNL}}
+\newcommand{\mNL}{\ComplexityFont{mNL}}
+\newcommand{\mNP}{\ComplexityFont{mNP}}
+\newcommand{\ModkL}{{\ComplexityFont{Mod}_k\ComplexityFont{L}}}
+\newcommand{\ModkP}{{\ComplexityFont{Mod}_k\ComplexityFont{P}}}
+\newcommand{\ModP}{\ComplexityFont{ModP}}
+\newcommand{\mP}{\ComplexityFont{mP}}
+\newcommand{\MP}{\ComplexityFont{MP}}
+\newcommand{\MPC}{\ComplexityFont{MPC}}
+\newcommand{\mTC}{\ComplexityFont{mTC}}
+
+% N
+\newcommand{\NC}{\ComplexityFont{NC}}
+\newcommand{\coNE}{\ComplexityFont{coNE}}
+\newcommand{\NE}{\ComplexityFont{NE}}
+\newcommand{\NEE}{\ComplexityFont{NEE}}
+\newcommand{\NEEE}{\ComplexityFont{NEEE}}
+\newcommand{\NEEXP}{\ComplexityFont{NEEXP}}
+\newcommand{\coNEXP}{\ComplexityFont{coNEXP}}
+\newcommand{\NEXP}{\ComplexityFont{NEXP}}
+\newcommand{\coNL}{\ComplexityFont{coNL}}
+\newcommand{\NL}{\ComplexityFont{NL}}
+\newcommand{\NLIN}{\ComplexityFont{NLIN}}
+\newcommand{\coNP}{\ComplexityFont{coNP}}
+\newcommand{\NP}{\ComplexityFont{NP}}
+\newcommand{\NPC}{\ComplexityFont{NPC}}
+\newcommand{\NPI}{\ComplexityFont{NPI}}
+\newcommand{\NPSPACE}{\ComplexityFont{NPSPACE}}
+\newcommand{\coNQP}{\ComplexityFont{coNQP}}
+\newcommand{\NQP}{\ComplexityFont{NQP}}
+\newcommand{\NSPACE}{\ComplexityFont{NSPACE}}
+\newcommand{\NTIME}{\ComplexityFont{NTIME}}
+
+% O
+\newcommand{\Opt}{\ComplexityFont{Opt}}
+\newcommand{\OptP}{\Opt\P}
+
+% P
+\newcommand{\PAC}{\ComplexityFont{PAC}}
+\newcommand{\PCD}{\ComplexityFont{PCD}}
+\newcommand{\PCP}{\ComplexityFont{PCP}}
+\newcommand{\Ppoly}{\P/\poly}
+\newcommand{\PH}{\ComplexityFont{PH}}
+\newcommand{\PEXP}{\ComplexityFont{PEXP}}
+\newcommand{\PL}{\ComplexityFont{PL}}
+\newcommand{\PP}{\ComplexityFont{PP}}
+\newcommand{\PPSPACE}{\ComplexityFont{PPSPACE}}
+\newcommand{\p}{\ComplexityFont{p}}
+\newcommand{\Promise}{\ComplexityFont{Promise}}
+\newcommand{\PromiseBPP}{\ComplexityFont{PromiseBPP}}
+\newcommand{\PromiseBQP}{\ComplexityFont{PromiseBQP}}
+\newcommand{\PromiseP}{\ComplexityFont{PromiseP}}
+\newcommand{\PromiseRP}{\ComplexityFont{PromiseRP}}
+\newcommand{\PrSPACE}{\ComplexityFont{PrSPACE}}
+\newcommand{\PSPACE}{\ComplexityFont{PSPACE}}
+\newcommand{\PT}{\ComplexityFont{PT}}
+\newcommand{\PTAS}{\ComplexityFont{PTAS}}
+\newcommand{\PTWK}{\ComplexityFont{PT/WK}}
+
+% Q
+\newcommand{\QAC}{\ComplexityFont{QAC}}
+\newcommand{\QACC}{\ComplexityFont{QACC}}
+\newcommand{\QAM}{\ComplexityFont{QAM}}
+\newcommand{\QCFL}{\ComplexityFont{QCFL}}
+\newcommand{\QCMA}{\ComplexityFont{QCMA}}
+\newcommand{\QH}{\ComplexityFont{QH}}
+\newcommand{\QIP}{\ComplexityFont{QIP}}
+\newcommand{\QMA}{\ComplexityFont{QMA}}
+\newcommand{\QMAM}{\ComplexityFont{QMAM}}
+\newcommand{\QMIP}{\ComplexityFont{QMIP}}
+\newcommand{\QNC}{\ComplexityFont{QNC}}
+\newcommand{\QP}{\ComplexityFont{QP}}
+\newcommand{\QPSPACE}{\ComplexityFont{QPSPACE}}
+
+% R
+\newcommand{\R}{\ComplexityFont{R}}
+\newcommand{\coRE}{\ComplexityFont{coRE}}
+\newcommand{\RE}{\ComplexityFont{RE}}
+\newcommand{\REG}{\ComplexityFont{REG}}
+\newcommand{\RL}{\ComplexityFont{RL}}
+\newcommand{\coRNC}{\ComplexityFont{coRNC}}
+\newcommand{\RNC}{\ComplexityFont{RNC}}
+\newcommand{\coRP}{\ComplexityFont{coRP}}
+\newcommand{\RP}{\ComplexityFont{RP}}
+\newcommand{\RSPACE}{\ComplexityFont{RSPACE}}
+
+% S
+\newcommand{\SAC}{\ComplexityFont{SAC}}
+\newcommand{\SC}{\ComplexityFont{SC}}
+\newcommand{\SE}{\ComplexityFont{SE}}
+\newcommand{\SEH}{\ComplexityFont{SEH}}
+\newcommand{\SKC}{\ComplexityFont{SKC}}
+\newcommand{\SIZE}{\ComplexityFont{SIZE}}
+\newcommand{\SPACE}{\ComplexityFont{SPACE}}
+\newcommand{\SL}{\ComplexityFont{SL}}
+\newcommand{\coSL}{\ComplexityFont{coSL}}
+\newcommand{\SPARSE}{\ComplexityFont{SPARSE}}
+\newcommand{\SPL}{\ComplexityFont{SPL}}
+\newcommand{\SPP}{\ComplexityFont{SPP}}
+\newcommand{\SUBEXP}{\ComplexityFont{SUBEXP}}
+\newcommand{\SZK}{\ComplexityFont{SZK}}
+
+% T
+\newcommand{\TC}{\ComplexityFont{TC}}
+
+% U
+\newcommand{\coUP}{\ComplexityFont{coUP}}
+\newcommand{\UP}{\ComplexityFont{UP}}
+
+% V
+
+% W
+\newcommand{\W}{\ComplexityFont{W}}
+
+% X
+\newcommand{\ZPE}{\ComplexityFont{ZPE}}
+\newcommand{\ZPP}{\ComplexityFont{ZPP}}
+\newcommand{\ZPTIME}{\ComplexityFont{ZPTIME}}
+
+%%%%%%% Extended Classes
+\ifthenelse{\boolean{complexity@fullmode}}{ %THEN we do ALL the classes
+
+% A
+\newcommand{\A}{\ComplexityFont{A}}
+\newcommand{\AlgP}{\ComplexityFont{AlgP}}
+\newcommand{\Amp}{\ComplexityFont{Amp}}
+\newcommand{\AmpMP}{\ComplexityFont{AmpMP}}
+\newcommand{\AmpPBQP}{\ComplexityFont{AmpPBQP}}
+\newcommand{\APP}{\ComplexityFont{APP}}
+\newcommand{\APX}{\ComplexityFont{APX}}
+\newcommand{\AUCSPACE}{\ComplexityFont{AUC\complexity@hyphen SPACE}}
+\newcommand{\AuxPDA}{\ComplexityFont{AuxPDA}}
+\newcommand{\AVBPP}{\ComplexityFont{AVBPP}}
+\newcommand{\AvE}{\ComplexityFont{AvE}}
+\newcommand{\AvP}{\ComplexityFont{AvP}}
+\newcommand{\AW}{\ComplexityFont{AW}}
+\newcommand{\AWPP}{\ComplexityFont{AWPP}}
+
+% B
+\newcommand{\betaP}{\beta\ComplexityFont{P}}
+\newcommand{\BP}{\ComplexityFont{BP}}
+
+\newcommand{\BPPpath}{{\ComplexityFont{BPP}_{\complexity@kern\ComplexityFont{path}}}}
+
+\newcommand{\BPHSPACE}{{\ComplexityFont{BP_{H}SPACE}}}
+\newcommand{\BPL}{\ComplexityFont{BPL}}
+\newcommand{\BPPOBDD}{\ComplexityFont{BPP\complexity@hyphen OBDD}}
+\newcommand{\BPQP}{\ComplexityFont{BPQP}}
+\newcommand{\kBQBP}{k\complexity@hyphenright\ComplexityFont{BQBP}}
+\newcommand{\BQNC}{\ComplexityFont{BQNC}}
+\newcommand{\BQNP}{\ComplexityFont{BQNP}}
+\newcommand{\BQPOBDD}{\ComplexityFont{BQP\complexity@hyphen OBDD}}
+\newcommand{\kBWBP}{k\complexity@hyphenright\ComplexityFont{BWBP}}
+
+% C
+%\newcommand{\Check}{\ComplexityFont{Check}} this has conflicts with amsmath
+\newcommand{\CLOG}{\ComplexityFont{CLOG}}
+\newcommand{\CNP}{\ComplexityFont{CNP}}
+\newcommand{\cofrIP}{\ComplexityFont{cofrIP}}
+\newcommand{\Coh}{\ComplexityFont{Coh}}
+\newcommand{\compIP}{\ComplexityFont{compIP}}
+\newcommand{\compNP}{\ComplexityFont{compNP}}
+\newcommand{\coUCC}{\ComplexityFont{coUCC}}
+\newcommand{\CP}{\ComplexityFont{CP}}
+\newcommand{\CSL}{\ComplexityFont{CSL}}
+\newcommand{\CZK}{\ComplexityFont{CZK}}
+
+% D
+\newcommand{\D}{\ComplexityFont{D}}
+\newcommand{\DCFL}{\ComplexityFont{DCFL}}
+\newcommand{\DiffAC}{\ComplexityFont{DiffAC}}
+\newcommand{\DisNP}{\ComplexityFont{DisNP}}
+\newcommand{\DistNP}{\ComplexityFont{DistNP}}
+\newcommand{\DP}{\ComplexityFont{DP}}
+\newcommand{\DQP}{\ComplexityFont{DQP}}
+\newcommand{\Dyn}{\ComplexityFont{Dyn}}
+\newcommand{\DynFO}{\ComplexityFont{Dyn\complexity@hyphenright FO}}
+
+% E
+\newcommand{\EL}{\ComplexityFont{EL}}
+\newcommand{\ELEMENTARY}{\ComplexityFont{ELEMENTARY}}
+\newcommand{\ELkP}{{\ComplexityFont{EL}_{k}\ComplexityFont{P}}}
+\newcommand{\kEQBP}{k\complexity@hyphenright\ComplexityFont{EQBP}}
+\newcommand{\EQP}{\ComplexityFont{EQP}}
+\newcommand{\EQTIME}{\ComplexityFont{EQTIME}}
+\newcommand{\EQBP}{\ComplexityFont{EQBP}}
+\newcommand{\ExistsBPP}{\ComplexityFont{ExistsBPP}}
+\newcommand{\ExistsNISZK}{\ComplexityFont{ExistsNISZK}}
+
+
+% F
+\newcommand{\FBQP}{\ComplexityFont{FBQP}}
+\newcommand{\Few}{\ComplexityFont{Few}}
+\newcommand{\FewP}{\ComplexityFont{FewP}}
+\newcommand{\FH}{\ComplexityFont{FH}}
+\newcommand{\FO}{\ComplexityFont{FO}}
+\newcommand{\FOLL}{\ComplexityFont{FOLL}}
+\newcommand{\FPR}{\ComplexityFont{FPR}}
+\newcommand{\FPT}{\ComplexityFont{FPT}}
+\newcommand{\FPTAS}{\ComplexityFont{FPTAS}}
+\newcommand{\FPTnu}{{\ComplexityFont{FPT}_{\complexity@kern\ComplexityFont{nu}}}}
+\newcommand{\FPTsu}{{\ComplexityFont{FPT}_{\complexity@kern\ComplexityFont{su}}}}
+\newcommand{\frIP}{\ComplexityFont{frIP}}
+\newcommand{\FTAPE}{\ComplexityFont{F\complexity@hyphen TAPE}}
+\newcommand{\FTIME}{\ComplexityFont{F\complexity@hyphen TIME}}
+
+%G
+\newcommand{\G}{\ComplexityFont{G}}
+\newcommand{\GANSPACE}{\ComplexityFont{GAN\complexity@hyphen SPACE}}
+\newcommand{\GC}{\ComplexityFont{GC}}
+\newcommand{\GCSL}{\ComplexityFont{GCSL}}
+\newcommand{\GPCD}{\ComplexityFont{GPCD}}
+
+% H
+\newcommand{\HkP}{{\ComplexityFont{H}_k\ComplexityFont{P}}}
+\newcommand{\HVSZK}{\ComplexityFont{HVSZK}}
+
+% I
+\newcommand{\IC}{\ComplexityFont{IC}}
+\newcommand{\IPP}{\ComplexityFont{IPP}}
+
+% J
+% What? No "J" classes?
+
+% K
+
+% L
+\newcommand{\LkP}{{\ComplexityFont{L}_k\ComplexityFont{P}}}
+\newcommand{\LOGCFL}{\ComplexityFont{LOGCFL}}
+\newcommand{\LOGNP}{\ComplexityFont{LOGNP}}
+\newcommand{\LOGSNP}{\ComplexityFont{LOGSNP}}
+\newcommand{\LWPP}{\ComplexityFont{LWPP}}
+
+% M
+\newcommand{\M}{\ComplexityFont{M}}
+\newcommand{\ModZkL}{{\ComplexityFont{ModZ}_k\ComplexityFont{L}}}
+\newcommand{\MkP}{{\ComplexityFont{(M}_k\ComplexityFont{)P}}}
+
+% N
+\newcommand{\NAuxPDA}{\ComplexityFont{NAuxPDA}}
+\newcommand{\NIPZK}{\ComplexityFont{NIPZK}}
+\newcommand{\NIQPZK}{\ComplexityFont{NIQPZK}}
+\newcommand{\NIQSZK}{\ComplexityFont{NIQSZK}}
+\newcommand{\NISZK}{\ComplexityFont{NISZK}}
+\newcommand{\NLOG}{\ComplexityFont{NLOG}}
+\newcommand{\NPMV}{\ComplexityFont{NPMV}}
+\newcommand{\NPMVsel}{\ComplexityFont{NPMV\complexity@hyphenleft sel}}
+\newcommand{\NPO}{\ComplexityFont{NPO}}
+\newcommand{\NPOPB}{\ComplexityFont{NPOPB}}
+\newcommand{\NPSV}{\ComplexityFont{NPSV}}
+\newcommand{\NPSVsel}{\ComplexityFont{NPSV\complexity@hyphenleft sel}} %don't use a \complexity@hyphen here, it looks bad
+\newcommand{\NT}{\ComplexityFont{NT}}
+
+% O
+\newcommand{\OBDD}{\ComplexityFont{OBDD}}
+\newcommand{\OCQ}{\ComplexityFont{OCQ}}
+
+% P
+\newcommand{\PBP}{\ComplexityFont{PBP}}
+\newcommand{\kPBP}{k\complexity@hyphenright\ComplexityFont{PBP}} %don't use a \complexity@hyphen here, it looks bad
+\newcommand{\Pclose}{\ComplexityFont{P\complexity@hyphenleft close}}
+\newcommand{\PermUP}{\ComplexityFont{PermUP}}
+\newcommand{\PF}{\ComplexityFont{PF}}
+\newcommand{\PFCHK}{\ComplexityFont{PFCHK}}
+\newcommand{\PhP}{\ComplexityFont{PhP}}
+\newcommand{\PINC}{\ComplexityFont{PINC}}
+\newcommand{\PIO}{\ComplexityFont{PIO}}
+\newcommand{\PKC}{\ComplexityFont{PKC}}
+\newcommand{\PLF}{\ComplexityFont{PL}}
+\newcommand{\PLL}{\ComplexityFont{PLL}}
+\newcommand{\PLS}{\ComplexityFont{PLS}}
+\newcommand{\POBDD}{\ComplexityFont{P\complexity@hyphen OBDD}}
+\newcommand{\PODN}{\ComplexityFont{PODN}}
+\newcommand{\polyL}{\ComplexityFont{polyL}}
+\newcommand{\PostBQP}{\ComplexityFont{PostBQP}}
+\newcommand{\PPA}{\ComplexityFont{PPA}}
+\newcommand{\PPAD}{\ComplexityFont{PPAD}}
+\newcommand{\PPADS}{\ComplexityFont{PPADS}}
+\newcommand{\PPP}{\ComplexityFont{PPP}}
+\newcommand{\PQUERY}{\ComplexityFont{PQUERY}}
+\newcommand{\PR}{\ComplexityFont{PR}}
+\newcommand{\PrHSPACE}{{\ComplexityFont{Pr}_{\ComplexityFont{H}}\ComplexityFont{SPACE}}}
+\newcommand{\promiseBPP}{\ComplexityFont{promiseBPP}}
+\newcommand{\promiseBQP}{\ComplexityFont{promiseBQP}}
+\newcommand{\promiseP}{\ComplexityFont{promiseP}}
+\newcommand{\promiseRP}{\ComplexityFont{promiseRP}}
+\newcommand{\PSel}{\ComplexityFont{P\complexity@hyphen Sel}}
+\newcommand{\PSK}{\ComplexityFont{PSK}}
+\newcommand{\PTAPE}{\ComplexityFont{PTAPE}}
+\newcommand{\PZK}{\ComplexityFont{PZK}}
+
+% Q
+\newcommand{\QPLIN}{\ComplexityFont{QPLIN}}
+\newcommand{\Qpoly}{\ComplexityFont{Qpoly}}
+\newcommand{\QMIPle}{{\ComplexityFont{QMIP}_{\complexity@kern\ComplexityFont{le}}}}
+\newcommand{\QMIPne}{{\ComplexityFont{QMIP}_{\complexity@kern\ComplexityFont{ne}}}}
+\newcommand{\QSZK}{\ComplexityFont{QSZK}}
+
+% R
+\newcommand{\RevSPACE}{\ComplexityFont{RevSPACE}}
+\newcommand{\RHL}{{\ComplexityFont{R}_{\ComplexityFont{H}}\ComplexityFont{L}}}
+\newcommand{\RHSPACE}{{\ComplexityFont{R}_{\ComplexityFont{H}}\ComplexityFont{SPACE}}}
+\newcommand{\RNP}{\ComplexityFont{RNP}}
+\newcommand{\RPP}{\ComplexityFont{RPP}}
+
+% S
+\newcommand{\SAPTIME}{\ComplexityFont{SAPTIME}}
+\newcommand{\SBP}{\ComplexityFont{SBP}}
+\newcommand{\Sel}{\ComplexityFont{Sel}}
+\newcommand{\SelfNP}{\ComplexityFont{SelfNP}}
+\newcommand{\SF}{\ComplexityFont{SF}}
+\newcommand{\SLICEWISEPSPACE}{\ComplexityFont{SLICEWISEPSPACE}}
+\newcommand{\SNP}{\ComplexityFont{SNP}}
+\newcommand{\SOE}{\ComplexityFont{SO\complexity@hyphen E}}
+\newcommand{\SP}{\ComplexityFont{SP}}
+\newcommand{\spanP}{\ComplexityFont{span}\complexity@hyphenright\ComplexityFont{P}}
+\newcommand{\symP}{\ComplexityFont{symP}}
+
+% T
+\newcommand{\TALLY}{\ComplexityFont{TALLY}}
+\newcommand{\TFNP}{\ComplexityFont{TFNP}}
+\newcommand{\ThC}{\ComplexityFont{ThC}}
+\newcommand{\TreeBQP}{\ComplexityFont{TreeBQP}}
+\newcommand{\TREEREGULAR}{\ComplexityFont{TREE\complexity@hyphen REGULAR}}
+
+%U
+\newcommand{\UAP}{\ComplexityFont{UAP}}
+\newcommand{\UCC}{\ComplexityFont{UCC}}
+\newcommand{\UL}{\ComplexityFont{UL}}
+\newcommand{\UE}{\ComplexityFont{UE}}
+\newcommand{\US}{\ComplexityFont{US}}
+
+% V
+\newcommand{\VNC}{\ComplexityFont{VNC}}
+\newcommand{\VNP}{\ComplexityFont{VNP}}
+\newcommand{\VP}{\ComplexityFont{VP}}
+\newcommand{\VQP}{\ComplexityFont{VQP}}
+
+% W
+\newcommand{\WAPP}{\ComplexityFont{WAPP}}
+\newcommand{\WPP}{\ComplexityFont{WPP}}
+
+% X
+\newcommand{\XORMIP}{{\ComplexityFont{XOR\complexity@hyphen MIP}^*[2,1]}}
+\newcommand{\XP}{\ComplexityFont{XP}}
+\newcommand{\XPuniform}{{\ComplexityFont{XP}_{\complexity@kern\ComplexityFont{uniform}}}}
+
+% Y
+\newcommand{\YACC}{\ComplexityFont{YACC}}
+
+% Z
+
+% We now include the user defined commands which must be in a file named
+% mycomplexity
+% We use this convention because the primitive \input may load packages
+% more than once, leading to unnecessary redefinitions and strange results
+
+}{}
+
+\InputIfFileExists{mycomplexity.sty}{}{\PackageWarning{complexity}{User Defined Commands file `mycomplexity.sty' not found, it will not be loaded.}}
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}
diff --git a/macros/latex/contrib/complexity/mycomplexity.sty b/macros/latex/contrib/complexity/mycomplexity.sty
new file mode 100644
index 0000000000..ab4297d10c
--- /dev/null
+++ b/macros/latex/contrib/complexity/mycomplexity.sty
@@ -0,0 +1,15 @@
+
+% Say I want to define a class, MCC (My Complexity Class)
+% I would use the following command:
+%
+% \newcommand{\MCC}{\ComplexityFont{MCC}}
+%
+% Then, in my actual document, I would use something like
+% $\MCC \subseteq \NP \cap \coNP$ to typeset it.
+%
+% In this file, you should also include any other standard inputs that you use.
+% For instance, I have a .tex file that defines a bunch of Math Mode shortcuts,
+% I would include it here as follows:
+
+
+\newcommand{\TIME}{\ComplexityFont{TIME}}
diff --git a/macros/latex/contrib/complexity/tableofclasses.tex b/macros/latex/contrib/complexity/tableofclasses.tex
new file mode 100644
index 0000000000..eb93e15052
--- /dev/null
+++ b/macros/latex/contrib/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 \\