summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/complexity/tableofclasses.tex
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/tableofclasses.tex
Initial commit
Diffstat (limited to 'macros/latex/contrib/complexity/tableofclasses.tex')
-rw-r--r--macros/latex/contrib/complexity/tableofclasses.tex685
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 \\