User:C. lorenz/Template:Infobox Complexity Class

PSPACE (example)
External pages	Complexity Zoo
Complete class	PSPACE-complete
Complement class	self
Equalities	AP, BPPSPACE, IP, NPSPACE, PPSPACE, SAPTIME
DTIME	,
Related	PTIME
Proper supersets	EXPSPACE
Improper supersets	AlmostPSPACE, EXPTIME, RG, QPSPACE
Inequalities	P-close, P/log
Improper subsets	CH, P^PP, P^#P, QSZK, RG[1]
Proper subsets	NL
Canonical problems	QSAT
Properties	Syntactic
Low with	self
Low for	self
Closed reductions	Poly-time
Models	Alternating Turing machine, Turing machine

Documentation[view] [edit] [history] [purge]

Usage edit

{{User:C. lorenz/Template: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=
}}

Parameter Explanation edit

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: " $n^{\Theta (1)}$ " (PTIME) or " $n^{\Omega (1)},2^{n^{O(1)}}$ " (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 edit

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.

Example References edit

^ Chandra, A.K. and Kozen, D.C. and Stockmeyer, L.J., 'Alternation', Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
^ Complexity Zoo, [1], accessed Mars 25, 2009
^ Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869–877. October 1992.
^ Savitch's theorem
^ ^a ^b Christos Papadimitriou (1985). ""Games against Nature"". "Journal of Computer and System Sciences". 31.
^ ^a ^b Space hierarchy theorem
^ Definition of Almost-PSPACE. PSPACE ⊆ PSPACE^A for every A.
^ Greg Kuperberg, Complexity Zoology: Active Inclusion Diagram, 2006, http://www.math.ucdavis.edu/~greg/zoology/diagram.xml
^ K. W. Wagner (1986). "The complexity of combinatorial problems with succinct representation". Informatica. 23: 325–356.
^ ^a ^b S. Toda (1989). "On the computational power of PP and ⊕P". FOCS 1989: 514–519.

User:C. lorenz/Template:Infobox Complexity Class

Contents

Usage edit

Parameter Explanation edit

Inclusion Guidelines edit

Example References edit

See also edit