الگو:کلاس‌های پیچیدگی

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

ن ب و کلاس‌های پیچیدگی مهم (بیشتر)
شدنی در نظر گرفته شده	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC P P-complete ZPP RP BPP BQP
مشکوک به شدنی	UP NP ان‌پی کامل ان‌پی سخت co-NP co-NP-complete AM PH PP #P #P-complete IP PSPACE PSPACE-complete
نشدنی در نظر گرفته شده	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
سلسله مراتب کلاسی	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetic hierarchy Boolean hierarchy
خاواده‌های کلاس‌ها	DTIME NTIME پیچیدگی فضا NSPACE Probabilistically checkable proof Interactive proof system