מחלקת סיבוכיות
אוסף בעיות בעלות סיבוכיות משותפת / ויקיפדיה האנציקלופדיה encyclopedia
במדעי המחשב ובתורת הסיבוכיות, מחלקת סיבוכיות היא אוסף בעיות בעלות סיבוכיות משותפת. בדרך כלל מחלקת סיבוכיות מוגדרת באופן הבא:
אוסף הבעיות שניתן לפתור על ידי מכונה מופשטת תוך שימוש ב- ממשאב , כאשר הוא גודל הקלט.
לדוגמה, המחלקה NP היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג לא-דטרמיניסטית בסיבוכיות זמן פולינומית, בעוד שהמחלקה PSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג דטרמיניסטית בסיבוכיות מקום פולינומית.