Computational Complexity

Abstract

This note introduces the notions of computational complexity, and the theory of NP Completeness in an informal and non-rigorous way. In designing decision support systems, the designers often use heuristics. For such designers, the ideas presented here provide sufficient conceptual clarity, and help them decide under which conditions and contexts, heuristic can be designed. The note focusses on optimization problems. It introduces Big-O notation, the classes P and NP of optimization problems, Cook’‘s theorem, and discusses how to prove that a problem is NP Complete.