Computational complexity and the P vs NP problem

Author(s)

Igor Carboni Oliveira

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2010-02-08

Examining board members

Arnaldo Vieira Moura; José Coelho de Pina Junior; Flávio Keidi Miyazawa

• Advisor: Arnaldo Vieira Moura

Abstract

Computational complexity theory is the field of theoretical computer science that aims to establish limits on the efficiency of algorithms. The main open question in computational complexity is the P vs NP problem. Intuitively, it states that, for several important computational problems, there is no algorithm that performs better than a trivial exhaustive search. We present here an introduction to the subject, followed by more recent and advanced results. In particular, the diagonalization method is discussed in detail. Although it is a classical technique in computational complexity, it is the only method that was able to separate strong complexity classes so far. Some of the most important results in computational complexity theory have been proven by diagonalization. In particular, Hartmanis and Stearns [54, 104] proved that, given more resources, one can solve more computational problems. These results are known as hierarchy theorems. We present a generalization of the deterministic hierarchy theorems, recovering the classical results proved by Hartmanis and Stearns as corollaries. This is the first time that such unified treatment is presented in the literature (AU)

• FAPESP's process: 08/07040-0 - Computational Complexity and the P vs NP Problem
• Grantee: Igor Carboni Oliveira
• Support Opportunities: Scholarships in Brazil - Master