diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/complexity |
Initial commit
Diffstat (limited to 'macros/latex/contrib/complexity')
-rw-r--r-- | macros/latex/contrib/complexity/README | 30 | ||||
-rw-r--r-- | macros/latex/contrib/complexity/complexity.pdf | bin | 0 -> 257609 bytes | |||
-rw-r--r-- | macros/latex/contrib/complexity/complexity.sty | 757 | ||||
-rw-r--r-- | macros/latex/contrib/complexity/complexity.tex | 493 | ||||
-rw-r--r-- | macros/latex/contrib/complexity/mycomplexity.sty | 15 | ||||
-rw-r--r-- | macros/latex/contrib/complexity/tableofclasses.tex | 685 |
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 Binary files differnew file mode 100644 index 0000000000..e83b01f00d --- /dev/null +++ b/macros/latex/contrib/complexity/complexity.pdf 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 \\ |