Category:Complexity classes

From Wikipedia, the free encyclopedia

The main article for this category is Complexity classes.

Pages in category "Complexity classes"

The following 74 pages are in this category, out of 74 total. Updates to this list can occasionally be delayed for a few days.

*

  • Complexity class
  • List of complexity classes

2

  • 2-EXPTIME

A

  • AC (complexity)
  • AC0
  • ACC (complexity)
  • APX
  • Almost Wide Probabilistic Polynomial-Time

B

  • BPP
  • BQP

C

  • Certificate (complexity)
  • Co-NP
  • Co-NP-complete
  • Co-RE
  • Co-RE-complete
  • Communication complexity

D

  • DLOGTIME

E

  • E (complexity)
  • ELEMENTARY
  • ESPACE
  • EXPSPACE
  • EXPTIME

F

  • FL (complexity)
  • FNP (complexity)

F cont.

  • FO (complexity)
  • FP (complexity)

G

  • GI (complexity)
  • GapP

I

  • IP (complexity)

L

  • L (complexity)
  • L/poly

N

  • NC (complexity)
  • NE (complexity)
  • NESPACE
  • NEXPTIME
  • NL (complexity)
  • NL-complete
  • NONELEMENTARY
  • NP (complexity)
  • NP-complete
  • NP-easy
  • NP-equivalent
  • NP-hard

P

  • P (complexity)
  • P = NP problem
  • P-complete
  • P/poly
  • PCP (complexity)
  • PH (complexity)

P cont.

  • PLS (complexity)
  • PP (complexity)
  • PPAD (complexity)
  • PR (complexity)
  • PSIZE
  • PSPACE
  • PSPACE-complete
  • PSPACE-hard
  • Parity P
  • PostBQP

R

  • R (complexity)
  • RE (complexity)
  • RE-complete
  • RLP
  • RP (complexity)

S

  • SL (complexity)
  • SNP (complexity)
  • Sharp-P
  • Sharp-P-complete
  • Strongly NP-complete

T

  • TFNP

U

  • UP (complexity)

W

  • Weakly NP-complete

Z

  • ZPL (complexity)
  • ZPP
Categories: Computational complexity theory
Views
  • Category
  • Discussion
  • Current revision
Navigation
  • Main Page
  • Contents
  • Featured content
  • Current events
Interaction
  • About Wikipedia
  • Community portal
  • Recent changes
  • Contact Wikipedia
  • Donate to Wikipedia
  • Help
Languages
  • Česky
  • Deutsch
  • Español
  • 한국어
  • Português
  • Русский
  • Српски / Srpski
  • 中文
Powered by MediaWiki
Wikimedia Foundation
  • This page was last modified 18:49, 1 November 2007 by Anonymous user(s) of Wikipedia. Based on work by Wikipedia user(s) Obradovic Goran, Ksyrie, Klutzy, MathMartin, Mormegil and Andris.
  • All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
    Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a U.S. registered 501(c)(3) tax-deductible nonprofit charity.
  • About Wikipedia
  • Disclaimers