الگو:ComplexityClasses

از ویکی‌پدیا، دانشنامهٔ آزاد

پرش به: ناوبری، جستجو

ن • ب • و Important complexity classes (more)

Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC P P-complete ZPP RP BPP BQP

Suspected infeasible	UP NP ان‌پی کامل ان‌پی سخت co-NP co-NP-complete AM PH PP #P #P-complete IP PSPACE PSPACE-complete

Considered infeasible	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL

Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetic hierarchy Boolean hierarchy

Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

منوی ناوبری