המחשב הוא בראש ובראשונה כלי, שהאדם מציב בפניו "בעיות" ומצפה לקבל את "פתרונותיהן". מדעי המחשב התיאורטיים נוסדו והתפתחו מתוך דיון בשאלות כגון:
1. מה הן "בעיות" ומה הם "פתרונות" עבורן?
2. אילו תהליכים מובילים מבעיה לפתרונה (בשפת הדיבור, תהליך כזה נקרא גם הוא "פתרון")?
3. האם יש פתרון לכל בעיה?
4. האם וכיצד ניתן לזהות פתרון בהינתן כזה?
5. האם עצם קיומו של פתרון לבעיה מבטיח אפשרות למצוא אותו?
6. מהי בעיה "קלה" או "קשה" לפתרון?
7. באילו יחידות נמדד הקושי של בעיה, ומה הם הכלים להערכתו?
8. באילו נסיבות נאמר שבעיה היא "קשה מדי" גם אם יש לה פתרון, ואילו "ויתורים" נהיה נכונים לעשות כדי להתמודד איתה בכל זאת, ולו באופן חלקי? 