Appendix CComplexity Theory
C.1 Introduction
Complexity theory studies the computational complexity of the problems and the algorithms solving them. In this appendix, we are interested in transmitting the main concepts and theoretical limits to algorithm efficiency coming from this theory. and drop some rigor in the description, for the sake of brevity and clarity.
Complexity theory deals with so called algorithmic problems, which are those that can be coded in a computer, and for which there is no ambiguity in distinguishing between correct and incorrect answers. This leaves aside, for instance, religious or philosophical problems. An algorithmic problem 
is defined by:
- A description of the possible problem input parameters, formallydescribed in any finite alphabet (the symbol set in our computer).
- A function that relates any possible input
for problem 
(which we call a problem instance), with one or more elements in a set of possible outputs: the right answers to that problem instance.
As an example, “Given a positive integer number 
, determine if it is prime” is the description ...
Get Optimization of Computer Networks now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
