Difference between revisions of "Complexity Zoo"

From Complexity Zoo
Jump to navigation Jump to search
m
 
(22 intermediate revisions by 14 users not shown)
Line 1: Line 1:
Previously many restaurants used posters to display their offers or menus. Just stick to the basics when you are still starting your business, and you can include more devices as your business expands. There are expert designers out there that can draw you great blueprints of awesome looking restaurant kitchen designs. Some of the leases allow the tenants not having to make any structure, eg roof, repairs in the last few years of the lease. If you are into relaxing with a drink after work, the restaurant has an early bird drink special every day. What are you waiting for? Interior designing is one major expenditure for a restaurant business in its earlier stages. An array of spectacular culinary delight awaits the diner. To drink, try a red wine, or a pisco sour (the national drink of lime brandy).<br><br>To increase the popularity of the restaurant you need to advertise it sufficiently. Of course, a creative restaurant kitchen would prove to be an ideal place for creative growth of the chefs! These hearty main dishes are typically served with choice of meat: chicken, pork or beef. By looking at the increasing popularity of management systems, many restaurant operators are using restaurant reservation systems combined with table management systems so that they can give their customers a better experience. This often creates a tussle over the capital invested and sharing of profits in the future. Probably the most distinguished reason of this progression is the fashionable pattern and fashion the way individuals love to consume out of their premises at some eating place.<br><br>Tell them about other items on the menu that they might enjoy instead. Don't be pushy and let the conversation gravitate towards your line of work. Once you register you are given a coupon that you can print and present to the restaurant when you visit them on your birthday. These restaurants may experience double-digit drop in year-to-year revenue. Some restaurant chains only operate, or are popular in a certain region. There is a need to screen the applicants carefully. September was a rough month for restaurant owners, but overall the industry expects that to turn around in the coming months.<br><br>Here is more in regards to [http://wiki.rs.uni-heidelberg.de/DanielleS Read This] look into http://Www.Kokchapress.net/blogs/user/SharronW47
+
__NOTOC__
 +
 
 +
==Introduction==
 +
 
 +
Welcome to the '''Complexity Zoo'''... There are now 545 classes and counting!
 +
[[Image:zoo.gif|thumb|right|200px|what's your problem?]]
 +
 
 +
{{CZ-Menu-Content}}
 +
 
 +
; Zookeeper : [http://www.scottaaronson.com/ Scott Aaronson]
 +
; Veterinarian : [http://www.math.ucdavis.edu/~greg/ Greg Kuperberg]
 +
; Zoo Conservationist : [https://www.linkedin.com/in/oliver-habryka-8a585297 Oliver Habryka] on behalf of the [https://www.lesswrong.com/ LessWrong] community
 +
 
 +
The Zoo first opened in 2002. It was made into a wiki in 2005, and hosted at the University of Waterloo from 2012 to 2020.
 +
 
 +
Errors?  Omissions?  Misattributions?  Your favorite class not here?  Then please contribute to the zoo as you see fit by [[Special:UserLogin | signing up]] and clicking on the edit links. Please include references, or better yet links to papers if available.
 +
 
 +
To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.)  Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our [[Help:Contents | simple wiki help page]].
 +
 
 +
If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson.com.
 +
 
 +
==See Also==
 +
 
 +
''Introductory Resources''
 +
* [[Zoo Intro|Introductory Essay]]: New visitors may want to stop here and see what the Zoo is all about.
 +
* [[Petting Zoo]]: A more gentle version of the Zoo with fewer classes, meant for new initiates in complexity. (If you're looking for where the Most Important Classes went, look in the Petting Zoo.)
 +
 
 +
''Other Collections and Resources''
 +
* [[Complexity Garden]]: Problems of interest in complexity theory and some notes about important inclusions.
 +
* [[Complexity Dojo]]: A collection of major theorems in complexity theory.
 +
* [[Zoo Exhibit|Special Exhibit]]: A collection of classes of quantum states and probability distributions.
 +
* [http://www.math.ucdavis.edu/~greg/zoology/intro.html Complexity Zoology]: A computer-assisted survey maintained by the [http://www.math.ucdavis.edu/~greg/ Greg Kuperberg], including [http://www.math.ucdavis.edu/~greg/zoology/diagram.xml active] and [http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf static] inclusion diagrams.
 +
* [http://satoshihada.wordpress.com/complexity-zoo-for-ipad/ Complexity Zoo for iPad (and iPhone)]: An iOS viewer for Complexity Zoo.
 +
 
 +
''Appendices''
 +
*[[Zoo Glossary|Glossary]]: Definitions of some complexity theoretic terms.
 +
*[[Zoo References|References]]: Bibliography for the Zoo.
 +
*[[Zoo Pronunciation|Pronunciation Guide]]: A resource for those who insist on communicating verbally about complexity.
 +
*[[Zoo Conventions|Conventions and Notation]]: Common notational conventions used here at the Zoo.
 +
*[[Zoo Operators|Operators]]: A (very short) list of operators which act upon classes.
 +
*[[Zoo Acknowledgments|Acknowledgments]]: Where the Zookeeper and friends acknowledge those who have helped out with the Zoo.
 +
*[[Meta:Complexity Zoo Contributor's Guide|Complexity Zoo Contributor's Guide]]: A guide on how to get started helping out with the Zoo.
 +
 
 +
''NB:'' Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram.  These references are obsolete until further notice.
 +
 
 +
<!-- Moved Most Important Classes to Petting Zoo -->
 +
 
 +
== All Classes ==
 +
{{CZ-Menu-Content}}
 +
 
 +
{{CZ-Letter-Section|Symbols}}
 +
{{CZ-Letter-Section|A}}
 +
{{CZ-Letter-Section|B}}
 +
{{CZ-Letter-Section|C}}
 +
{{CZ-Letter-Section|D}}
 +
{{CZ-Letter-Section|E}}
 +
{{CZ-Letter-Section|F}}
 +
{{CZ-Letter-Section|G}}
 +
{{CZ-Letter-Section|H}}
 +
{{CZ-Letter-Section|I}}
 +
<!--{{CZ-Letter-Section|J}}
 +
{{CZ-Letter-Section|K}}-->
 +
{{CZ-Letter-Section|L}}
 +
{{CZ-Letter-Section|M}}
 +
{{CZ-Letter-Section|N}}
 +
{{CZ-Letter-Section|O}}
 +
{{CZ-Letter-Section|P}}
 +
{{CZ-Letter-Section|Q}}
 +
{{CZ-Letter-Section|R}}
 +
{{CZ-Letter-Section|S}}
 +
{{CZ-Letter-Section|T}}
 +
{{CZ-Letter-Section|U}}
 +
{{CZ-Letter-Section|V}}
 +
{{CZ-Letter-Section|W}}
 +
{{CZ-Letter-Section|X}}
 +
{{CZ-Letter-Section|Y}}
 +
{{CZ-Letter-Section|Z}}
 +
 
 +
 
 +
{{CZ-Categories}}

Latest revision as of 02:46, 3 December 2020


Introduction

Welcome to the Complexity Zoo... There are now 545 classes and counting!

what's your problem?

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

Zookeeper
Scott Aaronson
Veterinarian
Greg Kuperberg
Zoo Conservationist
Oliver Habryka on behalf of the LessWrong community

The Zoo first opened in 2002. It was made into a wiki in 2005, and hosted at the University of Waterloo from 2012 to 2020.

Errors? Omissions? Misattributions? Your favorite class not here? Then please contribute to the zoo as you see fit by signing up and clicking on the edit links. Please include references, or better yet links to papers if available.

To create a new class, click on the edit link of the class before or after the one that you want to add and copy the format of that class. (The classes are alphabetized by their tag names.) Then add the class to the table of contents and increment the total number of classes. After this, you can use the side edit links to edit the individual sections. For more on using the wiki language, see our simple wiki help page.

If you would like to contribute but feel unable to make the updates yourself, email the zookeeper at scott at scottaaronson.com.

See Also

Introductory Resources

  • Introductory Essay: New visitors may want to stop here and see what the Zoo is all about.
  • Petting Zoo: A more gentle version of the Zoo with fewer classes, meant for new initiates in complexity. (If you're looking for where the Most Important Classes went, look in the Petting Zoo.)

Other Collections and Resources

Appendices

NB: Longtime Zoo watchers may recall Chris Bourke's LaTeX version of the Zoo and Chad Brewbaker's graphical inclusion diagram. These references are obsolete until further notice.


All Classes

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

Symbols

0-1-NPC - 1NAuxPDAp - 2-EXP - 3SUM-hard - #AC0 - #L - #L/poly - #GA - #P - #W[t] - ⊕EXP - ⊕L - ⊕L/poly - ⊕P - ⊕Pcc - ⊕SAC0 - ⊕SAC1

A

A0PP - AC - AC0 - AC0[m] - AC1 - ACC0 - AH - AL - ALL - ALOGTIME - AlgP/poly - Almost-NP - Almost-P - Almost-PSPACE - AM - AMcc - AMEXP - AM ∩ coAM - AM[polylog] - AmpMP - AmpP-BQP - AP - APP - APSPACE - APX - ASPACE - ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

B

βP - BC=P - BH - BPd(P) - BPE - BPEE - BPHSPACE(f(n)) - BPL - BP•NP - BPP - BPPcc - BPPcc - BPPKT - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BPP-OBDD - BPPpath - BPQP - BPSPACE(f(n)) - BPTIME(f(n)) - BQNC - BQNP - BQP - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQP-OBDD - BQPSPACE - BQPCTC - BQPtt/poly - BQTIME(f(n)) - k-BWBP

C

C=AC0 - C=L - C=P - CC - CC0 - CFL - CLOG - CH - Check - CL#P - CkP - CNP - coAM - coC=P - cofrIP - Coh - coMA - coModkP - compIP - compNP - coNE - coNEXP - coNL - coNP - coNPcc - coNP/poly - coNQP - coRE - coRNC - coRP - coSL - coSPARSE - coUCC - coUP - CP - cq-Σ2 - CSIZE(f(n)) - CSL - CSP - CZK

D

D#P - DCFL - Δ2P - δ-BPP - δ-RP - DET - DiffAC0 - DisNP - DistNP - DP - DQC1 - DQP - DSPACE(f(n)) - DTIME(f(n)) - DTISP(t(n),s(n)) - Dyn-FO - Dyn-ThC0

E

E - EE - EEE - EESPACE - EEXP - EH - ELEMENTARY - ELkP - EP - EPTAS - k-EQBP - EQP - EQPK - EQTIME(f(n)) - ESPACE - ∃BPP - ∃NISZK - EXP - EXP/poly - EXPSPACE

F

FBQP - FERT - FPERT - Few - FewEXP - FewP - FH - FIXP - FNL - FNL/poly - FNP - FO - FO(DTC) - FO(LFP) - FO(PFP) - FO(TC) - FO() - FOLL - FP - FPNP[log] - FPL - FPR - FPRAS - FPT - FPTnu - FPTsu - FPTAS - FQMA - frIP - F-TAPE(f(n)) - F-TIME(f(n))

G

GA - GAN-SPACE(f(n)) - GapAC0 - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

H

HalfP - HeurBPP - HeurBPTIME(f(n)) - HeurDTIME(f(n)) - HeurP - HeurPP - HeurNTIME(f(n)) - HkP - HVSZK

I

IC[log,poly] - IP - IPP - IP[polylog]

L

L - LC0 - LH - LIN - LkP - LOGCFL - LogFew - LogFewNL - LOGLOG - LOGNP - LOGSNP - L/poly - LWPP

M

MA - MAcc - MA' - MAC0 - MAE - MAEXP - mAL - MAPOLYLOG - MaxNP - MaxPB - MaxSNP - MaxSNP0 - mcoNL - MinPB - MIP - MIP* - MIPns - MIPEXP - (Mk)P - mL - MM - MMSNP - mNC1 - mNL - mNP - ModkL - ModL - ModkP - ModP - ModZkL - mP - MP - MPC - mP/poly - mTC0

N

NAuxPDAp - NC - NC0 - NC1 - NC2 - NE - NE/poly - Nearly-P - NEE - NEEE - NEEXP - NEXP - NEXP/poly - NIPZK - NIQSZK - NISZK - NISZKh - NL - NL/poly - NLIN - NLO - NLOG - NMCL - NONE - NNC(f(n)) - NP - NPC - NPC - NPcc - NPcc - NPI - NP ∩ coNP - (NP ∩ coNP)/poly - NP/log - NPMV - NPMV-sel - NPMVt - NPMVt-sel - NPO - NPOPB - NP/poly - (NP,P-samplable) - NPR - NPSPACE - NPSV - NPSV-sel - NPSVt - NPSVt-sel - NQL - NQL - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

O

OptP

P

P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pcc - PCD(r(n),q(n)) - P-Close - PCP(r(n),q(n)) - PDQP - PermUP - PEXP - PF - PFCHK(t(n)) - PH - PHcc - Φ2P - PhP - Π2P - PINC - PIO - PK - PKC - PL - PL1 - PL - PLF - PLL - PLS - PNP - PNPcc - P||NP - PNP[k] - PNP[log] - PNP[log^2] - P-OBDD - PODN - polyL - PostBPP - PostBPPcc - PostBQP - PP - PPcc - PP/poly - PPA - PPAD - PPADS - PPP - PPP - PPSPACE - PQMA[log] - PQUERY - PR - PR - PrHSPACE(f(n)) - PromiseBPP - PromiseBQP - PromiseP - PromiseRP - PromiseUP - PrSPACE(f(n)) - P-Sel - PSK - PSPACE - PSPACEcc - PSPACE/poly - PT1 - PTAPE - PTAS - PT/WK(f(n),g(n)) - PZK

Q

Q - QAC0 - QAC0[m] - QACC0 - QACf0 - QAM - QCFL - QCMA - QCPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA(2) - QMA1 - QMAlog - QMAM - QMA/qpoly - QMIP - QMIPle - QMIPne - QNC - QNC0 - QNCf0 - QNC1 - QP - QPH - QPLIN - QPSPACE - QRG - QRG(k) - QRG(2) - QRG(1) - QRL - QSZK

R

R - RBQP - RE - REG - RevSPACE(f(n)) - RG - RG[1] - RHL - RHSPACE(f(n)) - RL - RNC - RP - RPcc - RPcc - RPP - RQP - RSPACE(f(n))

S

S - S2P - S2-EXP•PNP - SAC - SAC0 - SAC1 - SAPTIME - SBP - SBPcc - SBQP - SC - SE - SEH - SelfNP - SFk - Σ2P - SKC - SL - SLICEWISE PSPACE - SNP - SO - SO(Horn) - SO(Krom) - SO(LFP) - SO(TC) - SO[] - SP - span-L - span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZKh

T

TALLY - TC0 - TFNP - Θ2P - TI - Tower - TreeBQP - TREE-REGULAR

U

UAMcc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UPcc - UPostBPPcc - UPPcc - US - USBPcc - UWAPPcc

V

VCk - VCOR - VNCk - VNPk - VPk - VPL - VQPk

W

W[1] - WAPP - WAPPcc - WHILE - W[P] - WPP - W[SAT] - W[*] - W[t] - W*[t]

X

XOR-MIP*[2,1] - XL - XNL - XP - XPuniform

Y

YACC - YP - YPP - YQP

Z

ZAMcc - ZBQP - ZK - ZPE - ZPP - ZPPcc - ZPTIME(f(n)) - ZQP