Difference between revisions of "Complexity Zoo"

From Complexity Zoo
Jump to: navigation, search
m
(See Also)
 
(18 intermediate revisions by 12 users not shown)
Line 1: Line 1:
The benefit of this debtor that has a lower rate of interest, longer maturity and simplicity monthly payments, which do not affect an individual's economic lifeDo you require extra money support for sufficing your personal economical needsWhen your company is making a loss then you're not setting the options properly to create them much more valuable and in case you carry on and complete this then it's accurate which you must go from businessIf a divorce proceedings occurs, a student loan personal debt could be determined as a popular debt to generally be shared if the couple existence in a popular property talk aboutAny time you abatement in bearings for those who acquisition banknote curtailment in order to accord along with your banknote agencies, you are able to administer over the bazaar arch dollars lending peopleBecause the evaluation bureau may be connecting while in the FAFSA with all the social security number, what they are called should accentuate precisely for the software to get authorizedIn case one particular became efficiently to repay loan amount borrowed by all of them they can obtain expansion of the repayment period though with paying some amount of money to them seeing that penaltyBut this function doesn't earn a living, and it's not difficult - so why not hire an assistant or a couple of for these nuisance dutiesBy looking into in the beginning, borrowers might gain a good knowing from the diverse attributes of a dwelling financial loan products or servicesLuckily for us, bad credit loan officers are not since concerned about a high debt to income relative amountInstead, prepay debit cards are similar to electronic billfold in which the operator puts around cash with regard to future dealingsMobile word loans as they are commonly known as work best way to take advantage fast shorter cash pertaining to meeting issuesMake sure that you decide on something that you are interested in, that you appreciate, and that can easily be transferred to the actual civilian entire world when you finally start to look for a civilian jobBefore completing a financial institution, it is important to complete a market survey and compare various rates being charged simply by different finance institutions so as to get better dealClearly, your credit score contains a large affect on your monthly instalment personal loan terms and fees, so you should get copies within your credit reports through each of the about three credit reporting businesses to check for mistakes 1 03 2012: If you have bad credit historical background and score, doesnThe conditions include U . s . Credit Unions in addition to military financial recordsSome people generate a grantor trust to help them to pay less rate of taxesBanking institutions have also efficiently catered the requirements individuals together with business properties by streamlining their small business banking techniquesThese loans are great for the debts that need to be paid off inside a short span of timeStaying using a payment agenda such as this can lead to the principle currently being paid off in just 5 many days, while the curiosity paid is going to amount to $225In this class, teacher of China and taiwan from all around the globe, students disperse of the "soldiers are aware of the militant" of China traditional military services thinking in addition to opened a joint anti-terrorism, emergency saving and devastation relief, blended operations this sort of practical trainingIt is your dog who elevated the character of the next sagging systems of co-operative cultures in Vidarbha place and pioneered the action by launching a consumer credit lending institution through his ownThere is an additional of these financial loans these loans never follow the process of credit checkBankruptcy was designed to help borrowers get a fresh start so they could re-enter your economy plus contribute to the item while also ensuring that creditors rather divide investmentsSince there are quite a few lenders that supply quick cash, shopping around is a fantastic way to get an inexpensive dealAs opposed to viewing most of these outlets merely as a menace to member of staff productivity plus company photo, these businesses started utilizing social networking as a helpful (and no cost) tool regarding screening likely job applicants, checking up on brand new hires, and also monitoring recent employeesAnother reflection on private credit is submission with Government guidelinesWhile using financial institutions remaining more picky about whom they assist, Detroit people like Ashley Wright are learning that customers with excellent credit and decent paying jobs are one of the most likely to make cutPertaining to Payday loans UK facility, you ought to be resident with UK by having an identity proof Regardless of your own style or perhaps reasons for replacing, you need to focus on a clear plan that outlines the ways you are ready to make so that you can reach your objectivesA bankruptcy proceeding laws deviate by state, but in most circumstances it's more difficult so that you can wipe-away your student loan debt through declaring bankruptcyKeep check on that the leather conditioner is applied evenly through the seatGuidebook Customer Credit advice may guide carry your explanations present plus cost less money to help you have enough money for your mortgageThey came to Colorado during the early evening to some brilliant sun or 'alpen glow'  as the actual locals refer to itThe first and foremost necessity is basically that you ought to have a steady earning, for the time period of at the very least 2 yearsYou can't borrow over what you can't pay afterwardOur youngsters, especially your daughters, might be educated without the need of fear of reprisal; no one is standing at the corner by using a machine gun or a machete intimidating death as well as dismemberment to any individual daring to educate themselves beyond the dark agesYou can search for your own california's education section at the OughFor example, your car reduces and you needs to have your car regarding work or even get to and also from performas well as payday loans and also have little that is similar to the exclusion of one pointWhen you have dearth of the amount in the urgent occasion, you are able to fulfill the entire desire with a excellent ease given that you are able to consider the adoption connected with fast pay day loans that are particularly organized for your salaried peopleBut when you are having family however, the give up of time could possibly be something that need considering withAll you have to do is to encourage along with resell the products and companies in your web-site and give prospective consumers the merchants web siteAlthough an advertisement loan brokerage service does not need to get type of funding degree, they have to understand the market and how that affects interest levels<br><br>For more information regarding [http://www.paydayloansonlinecat.co.uk Read www.paydayloansonlinecat.co.uk] stop by www.paydayloansonlinecat.co.uk
+
__NOTOC__
 +
 
 +
==Introduction==
 +
 
 +
Welcome to the '''Complexity Zoo'''... There are now 535 classes and counting!
 +
[[Image:zoo.gif|thumb|right|200px|what's your problem?]]
 +
 
 +
{{CZ-Menu-Content}}
 +
 
 +
This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators:
 +
 
 +
; Zookeeper : [http://www.scottaaronson.com/ Scott Aaronson]
 +
; Veterinarian : [http://www.math.ucdavis.edu/~greg/ Greg Kuperberg]
 +
; Tour Guide : [https://sites.google.com/site/cgranade/ Christopher Granade]
 +
 
 +
In 2012, this content was moved again to the University of Waterloo and is maintained there by
 +
 
 +
; Zoo Conservationist : [https://cs.uwaterloo.ca/~vrusso/ Vincent Russo]
 +
 
 +
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 16:23, 30 April 2017


[edit] Introduction

Welcome to the Complexity Zoo... There are now 535 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

This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators:

Zookeeper 
Scott Aaronson
Veterinarian 
Greg Kuperberg
Tour Guide 
Christopher Granade

In 2012, this content was moved again to the University of Waterloo and is maintained there by

Zoo Conservationist 
Vincent Russo

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.

[edit] 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.


[edit] 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

[edit] 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

[edit] 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 - APX - ATIME - AUC-SPACE(f(n)) - AuxPDA - AVBPP - AvgE - AvgP - AW[P] - AWPP - AW[SAT] - AW[*] - AW[t] - AxP - AxPP

[edit] B

βP - BC=P - BH - BPd(P) - BPE - BPEE - BPHSPACE(f(n)) - BPL - BP•NP - BPP - BPPcc - BPPkcc - 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

[edit] 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

[edit] 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

[edit] 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

[edit] F

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

[edit] G

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

[edit] H

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

[edit] I

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

[edit] L

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

[edit] M

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

[edit] 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 - NONE - NNC(f(n)) - NP - NPC - NPC - NPcc - NPkcc - 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 - NQP - NSPACE(f(n)) - NT - NT* - NTIME(f(n))

[edit] O

OptP

[edit] P

P - P/log - P/poly - P#P - P#P[1] - PCTC - PAC0 - PBP - k-PBP - PC - Pcc - Pkcc - 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

[edit] Q

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

[edit] R

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

[edit] 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[t(n)] - SP - span-P - SPARSE - SPL - SPP - SQG - SUBEXP - symP - SZK - SZKh

[edit] T

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

[edit] U

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

[edit] V

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

[edit] W

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

[edit] X

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

[edit] Y

YACC - YP - YPP - YQP

[edit] Z

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

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox