O'Reilly logo

Optimization of Computer Networks by Pablo Pavón Mariño

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required