Classificação e Complexidade de Problemas

Authors

Abstract

This report consists of an introduction to the theory of Computational Complexity, presenting to the reader some of the basic notions that allow for a deeper understanding of the questions raised by equating and solving problems, particularly when automatisms are involved. Thus, beginning with the formalization of some concepts that usually are used in a very informal way like, for instance, problem and algorithm, we proceed gradually towards a more profound insight on this theory. We will go through the most famous complexity classes and end with a short note on approximation algorithms.

Keywords

computational complexity

Subject

Computational complexity

Book

Classificação e Complexidade de Problemas, 972-8564-32-5, Departamento de Matemática, March 2001