Study on what computers can and cannot do. Focuses on answering why are some problems easy and others hard.
Decision Problems
A problem with a yes or no answer.
Examples:
- Given a number
n, isnprime? - Input is encoded as a string
- Output is yes or no
Solvable vs Practical Problems
Computability Theory
Studies whether a problem is solvable at all
Complexity Theory
Studies time and memory requirements. Some problems are solvable but impractical.