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 b3-math-0010 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 b3-math-0011 for problem b3-math-0012 (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 b3-math-0013, determine if it is prime” is the description ...

Get Optimization of Computer Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.