1 files changed, 685 insertions, 0 deletions
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 \\