Uma digressão em NP: como avaliar a complexidade de uma instância

Authors

Abstract

This dissertation presents a theorectical framework that allows for the derivation of a probabilistic model to performe an approximate evaluation for the instance's complexity of a combinatorial optimization problem. This means that, regardless of the inherent computacional classification of the problem, we quantify the individual complexity of particular instances. To this effect, it is first established that Shannon's entropy function can be used as an estimator for algorithmic complexity measures. Then we procced to define an appropriated probabilistic model to compute entropy values for instances of combinatorial optimization problems as a means to estimate its individual complexity. The question of defining the set of probability distribution is overcome by using the Maximum Entropy Principle. We conclude presenting some computational experiments to assert the practical applicability of this model to the evaluation of complexity for well known instances, not only for classical NP--hard but also for polynomial combinatorial problems.

Keywords

Computational Complexity, Algorithmic (Kolmogorov) complexity, Maximum Entropy

Subject

Computer Science

PhD Thesis

Uma digressão em NP: como avaliar a complexidade de uma instância, May 2004