רשימת מחלקות סיבוכיות

זוהי רשימה של מחלקות סיבוכיות בתורת הסיבוכיות. 

לרבות ממחלקות אלו יש שותף 'co' שמורכב מהשפות המשלימות של כל השפות במחלקה המקורית. למשל, אם שפה L היא ב NP אז המשלימה של L נמצאת ב- co-NP. (אין הכוונה שהמשלים של NP הוא co-NP—ישנן שפות שידוע כי נמצאות בשתי הקבוצות, ושפות אחרות שידוע שאינן נמצאות בשתיהן.)

הכינוי "הבעיות הקשות ביותר" של מחלקה, מתייחס לבעיות השייכות למחלקה כך שכל בעיה אחרת במחלקה זו ניתנת לרדוקציה אליה. יתר על כן, הרדוקציה היא גם כן בעיה במחלקה הנתונה, או של תת-קבוצה שלה.

קישורים חיצוניים 
 Complexity Zoo  - רשימה של מעל 400 מחלקות סיבוכיות והמאפיינים שלהן.

הערות שוליים 

מחלקות סיבוכיות
מחלקות סיבוכיות