# User:C. lorenz/Template:Infobox Complexity Class/doc

Template:Documentation subpage

## Usage

{{Infobox Complexity Class |class= |image= |long-name= |description= |external-urls= |wheredefined= |dtime= |complete-class= |complement-class= |proper-supersets= |improper-supersets= |equals= |related= |notequals= |improper-subsets= |proper-subsets= |properties= |low-with= |low-for= |closed-reductions= |closed-operations= |canonical-problems= |models= }}

{{#invoke:Infobox|infobox}}

## Parameter Explanation

Regarding the meaning of "minimal" and "maximal", see the paragraph of Inclusion Guidelines.

**class**: The (short) name of the class. Example: "NP" but not "Polynomial Time". Default: "[[{{PAGENAME}}]]".

**image**: Code for image, if any. Example: "[[File:Complexity_subsets_pspace.svg|200px]]" but not "File:Complexity_subsets_pspace.svg".

**long-name**: Paraphrased/full name or short description of the class. Example: "Non-deterministic polynomial time" but not "the set of all decision problems for which ...".

**description**: Longer description of the class. Not used.

**wheredefined**: First definitions of the class. If not available, any suitable place. Secondly, internet sources preferred. Leave this field out rather than linking to the wikipedia page of the class. Example: "<ref>Christos H. Papadimitriou, Games against nature, FOCS 1983</ref>" (definition of SAPTIME) or "<ref>Scott Aaronsson, [https://www.blogger.com/comment.g?blogID=17392898&postID=114560148725169634&pli=1 Shetl-Optimized, What is the name of this post?], 2006</ref>" (definition of YP - Yaroslav-Percival).

**external-urls**: Links to the class' entry at an external site that harbors entries for many classes. Example: "[http://qwiki.stanford.edu/wiki/Complexity_Zoo:N#np|Complexity Zoo]" but not links to for instance articles.

**dtime**: Functions *f* such that the class is in DTIME[*f*(*n*)], if applicable. Example: "" (PTIME) or "" (NP).

**complete-class**: The complete class under a suitable reduction or *none*.

**complement-class**: The complement class.

**proper-supersets**: (Minimal) classes containing our class and are known not to equal our class. Example: (for NP) "[[NEXP]], [[NP_(complexity)|NP]]/one" but not "[[PSPACE]]".

**improper-supersets**: (Minimal) classes containing our class but not known not to equal our class. Example: (for NP) "[[NE]], [[PSPACE]], [[MA]]".

**equals**: Classes equaling our class. Example: (for NP) "[[Probabilistically_checkable_proof_(complexity)|PCP]](<math>O(log n)</math>, 3), Existential [[Second-order logic]]".

**related**: Interesting related classes that does not fall in one of the other categories. Example: (for NP) "[[coNP]], [[FNP_(complexity)|FNP]]".

**notequals**: Classes that are known to not to equal our class but not known to be either supersets or subsets. Example: (for NP) "[[PTIME|P]]/log".

**improper-subsets**: (Maximal) classes contained by our class but not known to be different. Example: (for NP) "[[PTIME|P]]".

**proper-subsets**: (Maximal) classes contained by our class and known to be different. Example: (for PSPACE) "[[NL_(complexity)|NL]]".

**properties**: Interesting properties of the class. Example: (for NP) "syntactic".

**low-with**: Classes that are low to the class, i.e. A such that C^A = C.

**low-to**: Classes the class is low to, i.e. A such that A^C = A.

**closed-reductions**: (Maximal) reductions under which the class is closed. Example: (for NP) "[[Polynomial-time reduction|Poly-time]]" but not "Log-space" since NP is closed under polynomial-time reductions and log-space reductions are also polynomial-time reductions.

**closed-operations**: Notable operations under which the class is closed. Not used.

**canonical-problems**: A few select canonical problems. These should typically be complete problems whenever applicable.

**models**: Most noteworthy models of computation for which the class can be naturally defined. Example: (for NP) "[[Non-Deterministic Turing machine]], [[Descriptive complexity]]". As a guide, list only the three most important models for the class in the info box but any number in the article. For example, the descriptive complexity characterization of PH (PH = languages expressible with second-order logic) is much more natural than that of NP (second-order logic with only first-order universal quantification) and PSPACE (second-order logic with a transitive closure operator). It should therefore take less to omit "descriptive complexity" as a natural model of computation for NP than for PH.

## Inclusion Guidelines

*These guidelines are still in the making. WP:BB*

If all inclusions were listed in the relevant field, then most classes would have boxes with hundreds of names. The following suggestions are made to deal with this issue.

- Cite sources, even if taken from e.g. the Complexity Zoo.

- Inference based on basic set theory is considered "routine calculation" and is acceptable (see WP:NOR). In other words, if prof. X has published
*A*⊆*B*and prof. Y has published*B*⊆*C*, then we may correctly infer that*A*⊆*C*by referring to the two sources. Any inference that is not considered "routine" should be justified with a credible source explicating the inference.

- Do not include relations that can be reasonably inferred by following relations on the relevant pages, or relations that are of little interest and involves a class not defined on Wikipedia. For instance, if the page for class
*B*does not exist but the page of class*A*contains the relation*A*⊆*B*and the page of class*C*contains*B*⊆*C*, then it would still be reasonable to add*A*⊆*C*to the pages of both*A*and*C*. This would not be the case if*B*also listed the two relations. If*B*was defined but did not list these relations, then the page of*B*should be extended, not*A*or*C*. Even if the page of*B*does not exists, the relation involving*B*may be of interest. If there is another class*D*which has a relation to*C*that implies*B*⊆*C*, then one may reasonably replace the relation involving*B*with the relation involving*D*.

- Classes especially important
*for the class*may certainly violate the above guideline. For instance, one may very well include the relations of the complement, non-deterministic, or quantum equivalences even if the status of these classes are implied by other classes. This does not mean that P or NP should be included on every page.