Complexidade Computacional e o Problema P vs NP Este exemplar corresponde a` reda¸ca˜o final da Disserta¸ca˜o devidamente corrigida e defendida por Igor Carboni Oliveira e aprovada pela Banca Examinadora. Campinas, 10 de agosto de 2010. Prof. Dr. Arnaldo Vieira Moura (Orientador) Disserta¸ca˜o apresentada ao Instituto de Com- putac¸˜ao,unicamp,comorequisitoparcialpara a obten¸c˜ao do t´ıtulo de Mestre em Ciˆencia da Computa¸c˜ao. i FICHA CATALOGRÁFICA ELABORADA PELA BIBLIOTECA DO IMECC DA UNICAMP Bibliotecária: Silvania Renata de Jesus Ribeiro Cirilo – CRB8 / 6592 Oliveira, Igor Carboni Ol4c Complexidade computacional e o problema P vs NP/Igor Carboni Oliveira-- Campinas, [S.P. : s.n.], 2010. Orientador : Arnaldo Vieira Moura Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica. 1. Complexidade computacional. 2. Diagonalização. 3. Algoritmos.. I. Moura, Arnaldo Vieira. II. Universidade Estadual de Campinas. Instituto de Computação. III. Título. Título em inglês: Computational complexity and the P vs NP problem. Palavras-chave em inglês (Keywords): 1. Computational complexity. 2. Diagonalization. 3. Algorithms. Área de concentração: Teoria da Computação. Titulação: Mestre em Ciência da Computação. Banca examinadora: Prof. Dr. Arnaldo Vieira Moura – (IC-UNICAMP) Prof. Dr. Flávio Keidi Miyazawa – (IC-UNICAMP) Prof. Dr. José Coelho de Pina – (IME-USP) Prof. Dr. Julio César Lopez Hernandéz – (IC-UNICAMP) Profa. Dra. Ana Cristina Vieira de Melo - (IME-USP) Data da defesa: 02/08/2010 Programa de Pós-Graduação: Mestrado em Ciência da Computação. Instituto de Computa¸ca˜o Universidade Estadual de Campinas Complexidade Computacional e o Problema P vs NP Igor Carboni Oliveira1 Agosto de 2010 Banca Examinadora: • Prof. Dr. Arnaldo Vieira Moura (Orientador) • Prof. Dr. Fla´vio K. Miyazawa Instituto de Computa¸ca˜o - UNICAMP • Prof. Dr. Jos´e Coelho de Pina Instituto de Matema´tica e Estat´ıstica - USP • Prof. Dr. Julio C. Lo´pez Hern´andez (Suplente) Instituto de Computa¸ca˜o - UNICAMP • Profa. Dra. Ana Cristina Vieira de Melo (Suplente) Instituto de Matema´tica e Estat´ıstica - USP 1Suporte financeiro da Fundac¸˜ao de Amparo `a Pesquisa do Estado de S˜ao Paulo (2008/07040-0). iv Resumo A teoria de complexidade computacional procura estabelecer limites para a eficiˆencia dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O pro- blema P vs NP ´e uma quest˜ao central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por solu¸c˜oes ´e essencialmente a melhor alternativa algor´ıtmica poss´ıvel. Esta disserta¸ca˜o oferece tanto uma introdu¸c˜ao cl´assica ao tema, quanto uma exposi- ¸ca˜o a diversos teoremas mais avan¸cados, resultados recentes e problemas em aberto. Em particular, o m´etodo da diagonaliza¸c˜ao ´e discutido em profundidade. Os principais resultados obtidos por diagonaliza¸ca˜o s˜ao os teoremas de hierarquia de tempo e de espa¸co (Hartmanis e Stearns [54, 104]). Apresentamos uma generaliza¸ca˜o desses resultados, obtendo como corola´rios os teoremas cla´ssicos provados por Hartmanis e Stearns. Essa ´e a primeira vez que uma prova unificada desses resultados aparece na literatura. v 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 computati- onal 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 exhaus- tive 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. vi Pref´acio A complexidade computacional ´e uma disciplina fundamental para a ciˆencia da com- putac¸˜ao. Seus resultados sa˜o elegantes, profundos, e muitas vezes imprevis´ıveis. Espero, sinceramente, que parte do meu fasc´ınio e interesse por essa disciplina seja transmitido ao leitor. Esta disserta¸c˜ao de mestrado foi escrita para ser usada por estudantes interessados em aprender complexidade computacional. Existem excelentes livros [7, 47, 88, 103] sobre o tema na literatura. Meu objetivo foi escrever um texto em portuguˆes para ser usado de forma complementar a essas obras. Por isso, certos to´picos relevantes que s˜ao muito bem abordados nesses livros foram omitidos. Procurei destacar os m´etodos mais importantes e apresentar alguns resultados avan¸cados que n˜ao sa˜o discutidos em profundidade nesses textos. O u´nico pr´e-requisito para leitura da disserta¸c˜ao ´e um pouco de maturidade matema´- tica, embora uma exposic¸˜ao anterior a um curso de projeto e an´alise de algoritmos seja u´til. Para facilitar a leitura, a maioria das demonstra¸c˜oes s˜ao feitas em detalhes. Segue uma breve descri¸ca˜o de cada cap´ıtulo da disserta¸c˜ao. Cap´ıtulo 1: Introdu¸c˜ao. Neste cap´ıtulo introduzimos os principais conceitos utiliza- dos em complexidade computacional. Apo´s uma breve discussa˜o sobre os objetivos dessa disciplina, definimos o modelo computacional das M´aquinas de Turing. Essas m´aquinas formalizam a no¸ca˜o de algoritmo utilizada em complexidade computacional. A seguir, discutimos como medir a complexidade computacional de um algoritmo. Finalmente, mostramos como provar um limitante inferior envolvendo um tipo de ma´quina de Turing um pouco menos eficiente. Cap´ıtulo 2: Introdu¸c˜ao ao Problema P vs NP. Neste cap´ıtulo abordamos o prin- cipal problema em aberto da teoria de complexidade computacional: a rela¸ca˜o entre as classes de complexidade P e NP. Informalmente, o problema P vs NP procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por so- lu¸co˜es ´e essencialmente a melhor alternativa algor´ıtmica poss´ıvel. Apresentamos diversas vii formula¸c˜oes equivalentes para esse problema, al´em de discutirmos sua importˆancia e os principais m´etodos empregados na tentativa de resolvˆe-lo. Cap´ıtulo 3: Simula¸c˜ao e Diagonaliza¸c˜ao. Intuitivamente, esperamos que com mais recursos computacionais seja poss´ıvel resolver mais problemas. Os teoremas de hierarquia de tempo e de espac¸o, alguns dos resultados mais importantes provados em complexidade computacional, estabelecem exatamente isso. O argumento utilizado na prova desses te- oremas ´e conhecido como m´etodo da diagonaliza¸c˜ao. Neste cap´ıtulo vamos estudar essa t´ecnica em profundidade. Veremos tamb´em como generalizar e unificar a demonstrac¸˜ao dos teoremas de hierarquia e de outros resultados importantes em complexidade compu- tacional. Cap´ıtulo 4: O Problema P vs NP em Profundidade. Neste cap´ıtulo vamos dis- cutir alguns to´picos mais avanc¸ados relacionados com o problema P vs NP. Inicialmente, veremos como a hierarquia polinomial generaliza a defini¸ca˜o das classes de complexidade P e NP. Vamos mostrar tamb´em que algoritmos muito eficientes em tempo e espa¸co na˜o sa˜o capazes de decidir a linguagem SAT. Discutiremos em seguida algumas propriedades estruturais das linguagens em NP. Por u´ltimo, demonstraremos que existem algoritmos assintoticamente o´timos para todos os problemas da classe NP. Cap´ıtulo 5: Os Limites da Diagonaliza¸c˜ao. Veremos neste cap´ıtulo que alguns m´etodos discutidos nesta disserta¸c˜ao na˜o s˜ao capazes de resolver o problema P vs NP. Discutiremos em seguida como essa limita¸ca˜o se relaciona com resultados de indepen- dˆencia formal em matem´atica. Al´em disso, vamos estudar o comportamento de diversos problemas em aberto da complexidade computacional em universos computacionais al- ternativos. Finalmente, discutiremos como m´etodos mais modernos superam a limita¸ca˜o enfrentada por algumas das t´ecnicas estudadas anteriormente. Ressalvo que muitos resultados importantes envolvendo o problema P vs NP n˜ao esta˜o presentes. A complexidade computacional ´e uma a´rea extremamente ativa em teoria da computa¸c˜ao. Dado o meu conhecimento atual sobre o tema e o tempo dispon´ıvel, seria imposs´ıvel abordar com profundidade todos os desenvolvimentos recentes. Finalmente, qualquer cr´ıtica ou sugesta˜o sera´ muito bem-vinda. Tor¸co para que no futuro mais estudantes e pesquisadores brasileiros se interessem pelos problemas e desafios dateoriadecomplexidadecomputacional. Al´emdisso,esperoqueomeuesfor¸cotenhasido suficiente para que os resultados apresentados nesta disserta¸ca˜o possam ser entendidos em tempo polinomial no tamanho de cada demonstra¸ca˜o. viii Agradecimentos Aos meus pais, Carlos Magno de Oliveira e Helena Maria Carboni Oliveira, a` minha irm˜a, Iana Carboni Oliveira, e ao meu amor, Nayara Fonseca de Sa´, por tudo de especial que representam na minha vida. Ao meu orientador, professor Arnaldo Veira Moura, por ter me dado a oportunidade e liberdade para estudar diversos to´picos do meu interesse, por tantos conselhos s´abios ofe- recidos durante o mestrado, e por ter insistido constantemente para que eu melhorasse o texto final desta dissertac¸˜ao. Aos professores Walter Carnielli e Orlando Lee, meus orientadores durante a gradua¸ca˜o, por toda ajuda que me ofereceram naquele per´ıodo. Aos meus amigos dos primeiros anos de gradua¸ca˜o, agora f´ısicos e matem´aticos, por terem despertado meu interesse pelos aspectos mais teo´ricos e fundamentais da ciˆencia. Ao professor Cid Carvalho de Souza, por ter despertado meu interesse por complexidade computacional atrav´es de suas aulas de projeto e ana´lise de algoritmos. Ao Anderson de Arau´jo, por ter revisado os primeiros cap´ıtulos da disserta¸ca˜o. Aos funcion´arios do Instituto de Computac¸˜ao, por toda assistˆencia prestada durante os meus anos na Unicamp. ` A FAPESP, pelo suporte financeiro oferecido durante o mestrado. ix Sum´ario Resumo v Abstract vi Pref´acio vii Agradecimentos ix 1 Introdu¸c˜ao 1 1.1 Motiva¸ca˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Computabilidade vs Complexidade . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Complexidade Computacional . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 O Problema P vs NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Terminologia B´asica e Nota¸ca˜o . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 M´aquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 Eficiˆencia dos Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.8 Um Exemplo de Limitante Inferior . . . . . . . . . . . . . . . . . . . . . . 11 1.9 Referˆencias Adicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Introdu¸c˜ao ao Problema P vs NP 17 2.1 Introdu¸ca˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Defini¸ca˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Decisa˜o vs Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Uma Formula¸c˜ao Alternativa . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Reduc¸˜oes e Problemas Completos . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Importaˆncia Matem´atica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7 Principais Abordagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.8 Resultados Ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.9 Referˆencias Adicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 x