בעיה חישובית הינה מחלקה של פריטים של בעיות, כשלכל הפריטים מאפיינים דומים. לדוגמא: כפל (הקלט הוא שני מספרים, הפלט הרצוי הוא מכפלתם), שחמט (הקלט הוא עמדה במשחק שחמט, הפלט הרצוי הוא המסע הטוב בעמדה), מסלול קצר (הקלט הוא מפה עם מרחקים, נקודת התחלה ונקודת סיום, הפלט הרצוי הוא המסלול הקצר ביותר מההתחלה לסיום), קיפול חלבונים (הקלט הוא סדרה של חומצות אמיניות המהוות חלבון, הפלט הרצוי הוא המבנה המרחבי בעל האנרגיה המינימלית) וכדומה. אלגוריתם הינו מתכון בעזרתו ניתן לפתור את הבעיה החישובית באמצעות סדרה של צעדים בסיסיים (לדוגמא, מתכון לכפל שני מספרים מרובי ספרות באמצעות כפלים וחיבורים של ספרות בודדות). תחום הסיבוכיות החישובית מנסה לקבוע לאילו בעיות יש אלגוריתמים יעילים (בהם מספר הצעדים עולה בצורה מתונה עם גודל הקלט) ולאילו בעיות אין (בכל אלגוריתם מספר הצעדים יגדל בצורה אקספוננציאלית עם גודל הקלט). עבור רוב הבעיות החישוביות המקובלות ידוע סיווגן או כקלות או כקשות. מטרת המחקר שלי הייתה להבין טוב יותר מה גורם לבעיה חישובית להיות קשה. בין היתר, פיתחתי שיטות שמאפשרות לאפיין בעיות עבורן חישוב מקדים – כאשר רק חלק מהקלט נתון – אינו מסייע לחישוב הסופי. בנוסף, אפיינתי תכונות של קלטים (בפרט, תכונות הרחבה של גרפים) שגורמות לבעיות חישוביות להפוך מקשות לקלות.