ECM3422: Computability & Complexity

This course explores the theoretical foundations of computation, examining the fundamental properties, capabilities, and limitations of computers regardless of future hardware and software advances. It investigates computability to understand what can and cannot be computed by machines, identifying unsolvable problems that remain beyond the reach of any computer. The course also investigates complexity, differentiating between efficient and inefficient computation and introducing various complexity classes such as P, NP, NP-complete, and NP-hard. By understanding the limits of computation and efficiency, students will develop advanced problem-solving skills and the ability to design more elegant systems.