Artigo Complexidade

Complexidade Computacional e o Problema P vs NP
Este exemplar corresponde a` redacao final da

Dissertacao 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)
Dissertacao apresentada ao Instituto de Computacao, unicamp, como requisito parcial para

a obtencao do ttulo de Mestre em Ciencia da
Computacao.
FICHA CATALOGRFICA ELABORADA PELA

BIBLIOTECA DO IMECC DA UNICAMP
Bibliotecria: 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
Dissertao (mestrado) - Universidade Estadual de Campinas,
Instituto de Matemtica, Estatstica e Computao Cientfica.
1. Complexidade computacional. 2. Diagonalizao. 3. Algoritmos..
I. Moura, Arnaldo Vieira. II. Universidade Estadual de Campinas.
Instituto de Computao. III. Ttulo.
Ttulo em ingls: Computational complexity and the P vs NP problem.

Palavras-chave em ingls (Keywords): 1. Computational complexity. 2. Diagonalization. 3.
Algorithms.
rea de concentrao: Teoria da Computao.
Titulao: Mestre em Cincia da Computao.
Banca examinadora: Prof. Dr. Arnaldo Vieira Moura (IC-UNICAMP)
Prof. Dr. Flvio Keidi Miyazawa (IC-UNICAMP)
Prof. Dr. Jos Coelho de Pina (IME-USP)
Prof. Dr. Julio Csar Lopez Hernandz (IC-UNICAMP)
Profa. Dra. Ana Cristina Vieira de Melo - (IME-USP)
Data da defesa: 02/08/2010
Programa de Ps-Graduao: Mestrado em Cincia da Computao.
Instituto de Computacao
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. Flavio K. Miyazawa
Instituto de Computacao - UNICAMP
Prof. Dr. Jose Coelho de Pina
Instituto de Matematica e Estatstica - USP
Prof. Dr. Julio C. Lopez Hernandez (Suplente)
Instituto de Computacao - UNICAMP
Profa. Dra. Ana Cristina Vieira de Melo (Suplente)
Instituto de Matematica e Estatstica - USP
Suporte financeiro da Fundac

ao de Amparo à Pesquisa do Estado de Sao Paulo (2008/07040-0).
iv
Resumo
A teoria de complexidade computacional procura estabelecer limites para a eficiencia
dos algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema P vs NP e uma questao central em complexidade computacional. Informalmente,
ele procura determinar se, para uma classe importante de problemas computacionais, a
busca exaustiva por solucoes e essencialmente a melhor alternativa algortmica possvel.
Esta dissertacao oferece tanto uma introducao classica ao tema, quanto uma exposicao a diversos teoremas mais avancados, resultados recentes e problemas em aberto. Em
particular, o metodo da diagonalizacao e discutido em profundidade.
Os principais resultados obtidos por diagonalizacao sao os teoremas de hierarquia de
tempo e de espaco (Hartmanis e Stearns [54, 104]). Apresentamos uma generalizacao
desses resultados, obtendo como corolarios os teoremas classicos provados por Hartmanis
e Stearns. Essa e a primeira vez que uma prova unificada desses resultados aparece na
literatura.
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.
vi
Pref
acio
A complexidade computacional e uma disciplina fundamental para a ciencia da computacao. Seus resultados sao elegantes, profundos, e muitas vezes imprevisveis. Espero,
sinceramente, que parte do meu fascnio e interesse por essa disciplina seja transmitido
ao leitor.
Esta dissertacao 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 portugues para ser usado de
forma complementar a essas obras. Por isso, certos topicos relevantes que sao muito bem
abordados nesses livros foram omitidos. Procurei destacar os metodos mais importantes
e apresentar alguns resultados avancados que nao sao discutidos em profundidade nesses
textos.
Ou
nico pre-requisito para leitura da dissertacao e um pouco de maturidade matematica, embora uma exposicao anterior a um curso de projeto e analise de algoritmos seja
u
til. Para facilitar a leitura, a maioria das demonstracoes sao feitas em detalhes.
Segue uma breve descricao de cada captulo da dissertacao.
Captulo 1: Introduc
ao. Neste captulo introduzimos os principais conceitos utilizados em complexidade computacional. Apos uma breve discussao sobre os objetivos dessa
disciplina, definimos o modelo computacional das Maquinas de Turing. Essas maquinas
formalizam a nocao 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 maquina de Turing
um pouco menos eficiente.
Captulo 2: Introduc
ao ao Problema P vs NP. Neste captulo abordamos o principal problema em aberto da teoria de complexidade computacional: a relacao 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 solucoes e essencialmente a melhor alternativa algortmica possvel. Apresentamos diversas
vii
formulacoes equivalentes para esse problema, alem de discutirmos sua importancia e os

principais metodos empregados na tentativa de resolve-lo.
Captulo 3: Simulac
ao e Diagonalizac
ao. Intuitivamente, esperamos que com mais
recursos computacionais seja possvel resolver mais problemas. Os teoremas de hierarquia
de tempo e de espaco, alguns dos resultados mais importantes provados em complexidade
computacional, estabelecem exatamente isso. O argumento utilizado na prova desses teoremas e conhecido como metodo da diagonalizacao. Neste captulo vamos estudar essa
tecnica em profundidade. Veremos tambem como generalizar e unificar a demonstracao
dos teoremas de hierarquia e de outros resultados importantes em complexidade computacional.
Captulo 4: O Problema P vs NP em Profundidade. Neste captulo vamos discutir alguns topicos mais avancados relacionados com o problema P vs NP. Inicialmente,
veremos como a hierarquia polinomial generaliza a definicao das classes de complexidade
P e NP. Vamos mostrar tambem que algoritmos muito eficientes em tempo e espaco nao
sao capazes de decidir a linguagem SAT. Discutiremos em seguida algumas propriedades
estruturais das linguagens em NP. Por u
ltimo, demonstraremos que existem algoritmos
assintoticamente otimos para todos os problemas da classe NP.
Captulo 5: Os Limites da Diagonalizac
ao. Veremos neste captulo que alguns
metodos discutidos nesta dissertacao nao sao capazes de resolver o problema P vs NP.
Discutiremos em seguida como essa limitacao se relaciona com resultados de independencia formal em matematica. Alem disso, vamos estudar o comportamento de diversos
problemas em aberto da complexidade computacional em universos computacionais alternativos. Finalmente, discutiremos como metodos mais modernos superam a limitacao
enfrentada por algumas das tecnicas estudadas anteriormente.
Ressalvo que muitos resultados importantes envolvendo o problema P vs NP nao estao
presentes. A complexidade computacional e uma area extremamente ativa em teoria da
computacao. Dado o meu conhecimento atual sobre o tema e o tempo disponvel, seria
impossvel abordar com profundidade todos os desenvolvimentos recentes.
Finalmente, qualquer crtica ou sugestao sera muito bem-vinda. Torco para que no
futuro mais estudantes e pesquisadores brasileiros se interessem pelos problemas e desafios
da teoria de complexidade computacional. Alem disso, espero que o meu esforco tenha sido
suficiente para que os resultados apresentados nesta dissertacao possam ser entendidos em
tempo polinomial no tamanho de cada demonstracao.
viii
Agradecimentos
Aos meus pais, Carlos Magno de Oliveira e Helena Maria Carboni Oliveira, a` minha irma,
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 topicos do meu interesse, por tantos conselhos sabios oferecidos durante o mestrado, e por ter insistido constantemente para que eu melhorasse o
texto final desta dissertacao.
Aos professores Walter Carnielli e Orlando Lee, meus orientadores durante a graduacao,
por toda ajuda que me ofereceram naquele perodo.
Aos meus amigos dos primeiros anos de graduacao, agora fsicos e matematicos, por terem
despertado meu interesse pelos aspectos mais teoricos e fundamentais da ciencia.
Ao professor Cid Carvalho de Souza, por ter despertado meu interesse por complexidade
computacional atraves de suas aulas de projeto e analise de algoritmos.
Ao Anderson de Ara
ujo, por ter revisado os primeiros captulos da dissertacao.
Aos funcionarios do Instituto de Computacao, por toda assistencia prestada durante os
meus anos na Unicamp.
` FAPESP, pelo suporte financeiro oferecido durante o mestrado.
A
ix
Sum
ario
Resumo
Abstract
vi
Pref
acio
vii
Agradecimentos
ix
1 Introduc
ao
1.1 Motivacao . . . . . . . . . . . . . .
1.2 Computabilidade vs Complexidade
1.3 Complexidade Computacional . . .
1.4 O Problema P vs NP . . . . . . . .
1.5 Terminologia Basica e Notacao . .
1.6 Maquinas de Turing . . . . . . . .
1.7 Eficiencia dos Algoritmos . . . . . .
1.8 Um Exemplo de Limitante Inferior
1.9 Referencias Adicionais . . . . . . .
.
.
.
.
.
.
.
.
.
1
1
3
4
4
5
6
10
11
14
.
.
.
.
.
.
.
.
.
17
17
20
24
25
27
31
32
35
37
2 Introduc
ao ao Problema P vs NP
2.1 Introducao . . . . . . . . . . . . .
2.2 Definicao . . . . . . . . . . . . . .
2.3 Decisao vs Busca . . . . . . . . .
2.4 Uma Formulacao Alternativa . . .
2.5 Reducoes e Problemas Completos
2.6 Importancia Matematica . . . . .
2.7 Principais Abordagens . . . . . .
2.8 Resultados Basicos . . . . . . . .
2.9 Referencias Adicionais . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Simulac
ao e Diagonalizac
ao
3.1 Introducao . . . . . . . . . . . . . . .
3.2 Um Teorema Geral de Hierarquia . .
3.3 Consequencias do Resultado Anterior
3.4 O Teorema da Lacuna . . . . . . . .
3.5 A Hierarquia Nao-Determinstica . .
3.6 O Metodo da Completude . . . . . .
3.7 Referencias Adicionais . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 O Problema P vs NP em Profundidade
4.1 A Hierarquia Polinomial . . . . . . . . . .
4.2 Alternancia . . . . . . . . . . . . . . . . .
4.3 Cotas Inferiores para SAT . . . . . . . . .
4.4 Reducoes e NP coNP . . . . . . . . . . .
4.5 O Teorema de Ladner . . . . . . . . . . .
4.6 NP-Completude, Isomorfismo e Densidade
4.7 Algoritmos Otimos

para NP . . . . . . . .
4.8 Referencias Adicionais . . . . . . . . . . .
5 Os
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
Limites da Diagonalizac
ao
Introducao . . . . . . . . . . . . . . . . .
Uma Barreira Fundamental . . . . . . .
P vs NP e Resultados de Independencia
Resultados Adicionais . . . . . . . . . .
Oraculos Aleatorios . . . . . . . . . . . .
Relativizacao Positiva . . . . . . . . . .
O Argumento Contrario de Kozen . . . .
Possvel Superar a Relativizacao? . . .
E
Referencias Adicionais . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
39
44
49
51
53
55
57
.
.
.
.
.
.
.
.
59
59
66
70
74
77
81
86
88
.
.
.
.
.
.
.
.
.
91
91
94
96
99
100
102
103
104
106
6 Conclus
ao
107
Bibliografia
108
xi
Captulo 1
Introdu
c
ao
The most beautiful thing we can experience is the mysterious.
It is the source of all true art and science.
Albert Einstein.
Neste captulo introduzimos os principais conceitos utilizados em complexidade computacional. Apos uma breve discussao sobre os objetivos dessa disciplina, definimos o modelo computacional das Maquinas de Turing. Essas
maquinas formalizam a nocao 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 maquina de Turing um pouco menos eficiente.
1.1
Motivac
ao
Esta dissertacao de mestrado versa sobre uma das questoes mais profundas investigadas pela ciencia moderna. Antes de discutirmos a importancia do problema que vamos
estudar, convidamos o leitor a refletir sobre a seguinte questao:
Qual e o objetivo da ciencia da computacao?
De maneira geral, pode-se dizer que a ciencia da computacao procura entender as limitacoes e oportunidades oferecidas pelo nosso universo em relacao a nossa capacidade de
processar, armazenar e transmitir informacoes. Ainda que possa parecer ampla demais,
essa definicao ilustra razoavelmente bem a direcao das pesquisas em ciencia da compu1
Captulo 1. Introducao
tacao ao longo das decadas. Desde o advento dos primeiros computadores ate a epoca
das pesquisas em computacao quantica, tentamos entender e tirar vantagem do mundo
computacional ao nosso redor.
Embora a visao quantica do mundo traga consigo uma promessa de novas possiblidades
computacionais, diversos problemas fundamentais persistem no universo da computacao
classica, sendo que o mais importante deles e o problema P vs NP.
De modo fascinante, durante o seculo passado diversos pesquisadores mostraram que
existem barreiras fundamentais limitando a nossa capacidade de processar informacoes.
Por exemplo, demonstrou-se que existem problemas computacionais extremamente difceis. Em outras palavras, mesmo que pudessemos utilizar em conjunto os melhores
computadores atuais durante todo o tempo de vida do universo, nao seramos capazes de
encontrar solucoes para muitos problemas, embora elas existam.
A teoria de complexidade computacional procura classificar os problemas computaci uma disciplina relativamente recente,
onais de acordo com o seu grau de dificuldade. E
com muitos problemas em aberto e alguns resultados extraordinarios. O principal desafio
para os pesquisadores dessa disciplina e o desenvolvimento de metodos matematicos que
possam ser usados para provar que certos problemas computacionais sao inerentemente
difceis.
O problema P vs NP e uma questao central em complexidade computacional. Informalmente, ele procura determinar se, para uma classe importante de problemas computacionais, a busca exaustiva por solucoes e essencialmente a melhor alternativa algortmica
possvel. Infelizmente, essa nao e uma solucao viavel para milhares de problemas presentes
na fsica, biologica, matematica e outras disciplinas, mas e o melhor que sabemos fazer.
Apesar de ter sido intensamente estudado por decadas, o problema permanece em aberto.
Aparentemente, os metodos atuais utilizados em matematica e ciencia da computacao nao
sao suficientes para resolver o problema.
Sem d
uvida alguma, a solucao do problema P vs NP sera um grande passo para a cien razoavel supor que toda civilizacao avancada questionou em algum
cia da computacao. E
momento a sua habilidade de computar, de transformar informacao em conhecimento. E

fascinante presenciar o momento em que nos adquirimos conhecimento suficiente para formular uma questao tao fundamental como essa. Encontrar a resposta para o problema P
vs NP e um desafio a ser vencido pela ciencia moderna, fruto da razao e inteligencia humanas. Independentemente da resposta, sua solucao tera necessariamente que revolucionar
a matematica e a ciencia da computacao dos dias de hoje.
1.2. Computabilidade vs Complexidade
1.2
Computabilidade vs Complexidade
Apesar da nocao de algoritmo ser utilizada ha pelo menos dois mil anos, apenas no
seculo vinte o conceito de computacao foi formalmente definido e estudado. Isso ocorreu
principalmente devido a suspeita dos pesquisadores da epoca de que certos problemas
computacionais poderiam ser indecidveis por meio de computacao.
Para provar que um problema pode ser resolvido por um algoritmo, basta dar uma descricao detalhada de um procedimento finito capaz de resolver o problema computacional
em consideracao. Porem, para argumentar que determinada tarefa nao pode ser resolvida
por meio de computacao, torna-se necessaria a definicao formal do conceito de algoritmo.
Somente assim podemos provar que nenhum procedimento satisfazendo a definicao de
algoritmo e capaz de realizar a tarefa desejada.
Portanto, a primeira grande questao enfrentada pelos pesquisadores foi encontrar uma
definicao satisfatoria para esse conceito. De modo fascinante, verificou-se que todas as
definicoes propostas para a nocao de computacao eram equivalentes, ou seja, os diversos
modelos computacionais sugeridos resolviam o mesmo conjunto de problemas. Devido a
esse fato, a nocao de computacao se tornou um conceito cientfico robusto e fundamental.
A partir da definicao formal de algoritmo, amplamente aceita, os pesquisadores obtiveram sucesso em provar que existem problemas bem definidos que nao podem ser resolvidas
por meios algortmicos. A u
nica maneira de resolver esses problemas e abandonando algum requisito fundamental e indiscutvel da definicao de algoritmo, como o fato de um
programa de computador sempre terminar a sua computacao apos um n
umero finito de
passos, ou possuir uma descricao finita. A teoria de computabilidade tem como objetivo principal determinar quais problemas sao computaveis, ou seja, podem ser resolvidos
atraves de algoritmos.
A existencia de problemas indecidveis trouxe consequencias extraordinarias. Por
exemplo, a partir da indecidibilidade do problema da parada e possvel demonstrar que a
matematica e uma ciencia necessariamente incompleta. Isso significa que em qualquer axiomatizacao da matematica e possvel encontrar sentencas verdadeiras que nao podem ser
demonstradas a partir das regras e axiomas do sistema formal. Veja a secao de referencias
desta secao para mais detalhes.
A teoria de computabilidade fornece metodos para classificarmos quais problemas sao
solucionaveis por algoritmos. Por outro lado, a teoria de complexidade pode ser vista
como uma continuacao dessa disciplina, uma vez que ela particiona os problemas que
podem ser resolvidos por algoritmos em diversas classes, de acordo com a quantidade de
recursos computacionais necessarios e suficientes para resolver cada problema. Embora
a teoria de computabilidade seja uma disciplina fascinante, ela nao sera discutida nesta
dissertacao. Recomendamos que o leitor interessado em computabilidade procure alguma
referencia indicada na secao final deste captulo.
1.3
Complexidade Computacional
A complexidade computacional e a area da ciencia da computacao que procura determinar por quais motivos certos problemas decidveis sao tao difceis de serem resolvidos
por computadores. Essa disciplina, praticamente inexistente ha quarenta anos, expandiuse tremendamente e atualmente e responsavel por boa parte das atividades de pesquisa
em teoria da computacao.
Desde a decada de sessenta, quando o uso de computadores deixou de ser restrito
a poucas instituicoes cientficas, os programadores perceberam que a existencia de um
algoritmo (programa) para uma tarefa nao era suficiente para que ela pudesse ser resolvida
por um computador. Foram descobertos muitos problemas praticos para os quais os
melhores algoritmos conhecidos demoravam tanto tempo para executar que inviabilizava
completamente a busca de respostas para o problema atraves de meios computacionas. A
grande questao era se essas observacoes eram uma consequencia da nossa incapacidade de
encontrar um algoritmo mais eficiente para o problema ou se resultavam de dificuldade
inerente do problema em consideracao.
Essa situacao levou à ideia de se medir a dificuldade de determinadas tarefas com
respeito a` quantidade de recursos computacionais necessarios e suficientes para computalas. Isso, por sua vez, levou à classificacao dos problemas que podem ser resolvidos
algoritmicamente de acordo com o seu grau de dificuldade.
Os principais objetivos da teoria que estudaremos sao, portanto: estimar os recursos
computacionais necessarios e suficientes para solucionar problemas algortmicos concretos;
identificar e definir a nocao de eficiencia ou tratabilidade dos problemas computacionais; desenvolver metodos para classifica-los dentro de diversas classes de complexidade;
comparar a eficiencia de diversos modelos computacionais distintos.
1.4
O Problema P vs NP
A pesquisa em complexidade computacional pode ser dividida em dois grandes grupos.

Pode-se estudar a dificuldade de um problema computacional especfico, ou investigar
como certos recursos computacionais e classes de problemas estao relacionados. Apesar
dessa divisao, o estudo de classes de problemas pode muitas vezes ser reduzido ao estudo
de problemas individuais (completos) que capturam propriedades essenciais da classe.
O problema P vs NP insere-se exatamente nesse contexto. Denota-se por P o conjunto
de problemas computacionais com solucoes que podem ser encontradas de forma eficiente.
1.5. Terminologia Basica e Notacao
Por sua vez, a classe NP contem os problemas computacionais com solucoes que podem
ser verificadas de forma eficiente. Intuitivamente, o problema P vs NP pergunta como
essas duas classes estao relacionadas, ou seja, se para todo problema cujas solucoes sao
eficientemente checaveis tambem existe um algoritmo eficiente capaz de encontrar tais
solucoes. Apesar de ser uma questao envolvendo classes de problemas, a existencia de
problemas completos para a classe NP torna interessante o estudo de alguns problemas
computacionais especficos.
Dado um problema computacional pertencente a` classe NP, existe um algoritmo muito
simples capaz de resolve-lo. Ele procede da seguinte forma: gera todas as respostas
possveis para uma dada instancia do problema e entao aplica um algoritmo capaz de
checar essas respostas (a existencia desse u
ltimo e garantida pela definicao de NP). Uma
desvantagem dessa abordagem e que o algoritmo final nao e eficiente. Enunciado de outra
forma, o problema P vs NP procura responder se essa busca exaustiva por solucoes pode
ser sempre evitada. Embora a maioria dos pesquisadores acredite que a busca exaustiva
seja essencial, ninguem ate agora foi capaz de exibir uma prova matematica desse fato.
O problema P vs NP e de fundamental importancia na criptografia moderna. A seguranca da Internet e da maioria das transacoes financeiras depende de algumas hipoteses,
tais como a dificuldade inerente de se fatorar n
umeros inteiros muito grandes. Se P =
NP, essas hipoteses sao falsas e a seguranca de tais transacoes estaria comprometida.
A existencia de um algoritmo eficiente para algum problema NP-completo (veja a
secao 2.5) teria consequencias fantasticas nao so para a ciencia da computacao, mas tambem para muitas outras areas de natureza distinta. Por exemplo, isso transformaria a
matematica contemporanea, ao permitir que um computador encontrasse provas formais
de diversos teoremas que possuam uma demonstracao de tamanho razoavel (veja a secao 2.6). Essas consideracoes valem tambem para diversos outros trabalhos criativos que
atualmente listamos como inerentemente humanos. Esse e um problema fundamental na
inteligencia artificial, cuja solucao poderia ser facilitada se tivessemos algoritmos praticos
para problemas NP-completos.
1.5
Terminologia B
asica e Nota
c
ao
A notacao e os conceitos basicos utilizados no texto sao usuais em teoria da computacao

e podem ser encontrados nos livros de Arora e Barak [7] e Sipser [103], por exemplo. Por
conveniencia, apresentamos nesta secao as principais convencoes adotadas.
O smbolo N denota o conjunto dos n
umeros naturais. Se e um conjunto finito, entao
uma palavra sobre o alfabeto e uma sequencia finita de elementos de . Denotamos por
? o conjunto de todas as palavras sobre o alfabeto . O tamanho de uma palavra w sera
representado por |w|. Uma palavra w de tamanho k e um palndromo se e somente se
w = w1 w2 . . . wk = wk wk1 . . . w1 . O smbolo detona a palavra vazia. A concatenacao de

duas palavras w1 e w2 sera denotada por w1 w2 . Quando o alfabeto nao for especificado,
assuma que = {0, 1}.
Dado um objeto x, utilizaremos a notacao hxi para representar esse objeto como
uma palavra. Essa notacao sera usada para codificar inteiros, matrizes, vetores, etc. Em
particular, utilizaremos a notacao hx, yi para a palavra que representa o par formado pelos
facil perceber que
objetos x e y, e similarmente para uma quantidade maior de objetos. E
existem representacoes convenientes para todas as estruturas discutidas no texto atraves
do uso de palavras binarias. Se z e um vetor de elementos, seu i-esimo elemento sera
representado por zi .
Atraves da representacao de objetos arbitrarios por palavras poderemos identificar
qualquer funcao f : A B com domnio ou imagem que nao sejam palavras pela funcao
correspondente que utiliza a representacao por palavras dos objetos em A e B. A maior
parte das funcoes discutidas neste texto terao como imagem 0 ou 1.
Quando a imagem de uma funcao f for um u
nico bit, vamos identifica-la pelo conjunto
?
Lf = {x : f (x) = 1} {0, 1} . Todo subconjunto de ? e chamado de linguagem e
identificamos o problema computacional de computar f como sendo o problema de decidir
a linguagem Lf (dado x, verificar se x Lf ). Se L e uma linguagem sobre o alfabeto
, entao L = ? \L, ou seja, o complemento de L. Uma linguagem L e dita nao-trivial
quando L 6= e L 6= ? .
Denotaremos por log n o logaritmo do n
umero inteiro n na base 2. Dizemos que
uma propriedade P (n) definida sobre o conjunto dos n
umeros naturais e valida para n
suficientemente grande se existe algum n
umero inteiro N tal que P (n) vale para todo
n N . Se f, g : N N sao funcoes, entao dizemos que f = O(g) se existe uma
constante c tal que f (n) cg(n) para n suficientemente grande. Definimos que f = (g)
se g = O(f ), e escrevemos f = (g) quando temos f = O(g) e g = O(f ). Finalmente,
dizemos que f = o(g) se para todo > 0, f (n) g(n) para n suficientemente grande, e
escrevemos f = (g) quando g = o(f ).
Por u
ltimo, o nome de algumas classes de complexidade e de alguns conceitos importantes foram mantidos em ingles.
1.6
M
aquinas de Turing
um fato surpreendente a existencia de um modelo computacional aparentemente caE

paz de simular todos os modelos computacionais fisicamente implementaveis. Nesta secao
apresentamos uma definicao informal das maquinas de Turing, um modelo amplamente
utilizado em complexidade computacional. Para uma apresentacao formal e uma discussao abrangente sobre o papel das maquinas de Turing em computacao, recomendamos a
1.6. Maquinas de Turing
leitura de Sipser [103].

Um algoritmo e uma sequencia finita de passos elementares capaz de realizar uma
determinada tarefa computacional. Dizemos que uma funcao f : ? ? e computada
por um algoritmo A se, para todo x ? , A produz apos o termino de sua execucao
o resultado f (x). Nesse caso, dizemos que f e uma funcao computavel. Para qualquer
algoritmo, cada passo de sua computacao e proveniente de um conjunto finito de regras
elementares. Cada regra pode ser aplicada um n
umero arbitrario de vezes. Alem da
entrada x, o algoritmo tambem tem acesso a uma memoria arbitrariamente grande onde
pode desenvolver a sua computacao. Por ser uma abstracao conveniente, dizemos que A
tem acesso a uma memoria infinita. Essa memoria e dividida em celulas e cada celula
pode armazenar um smbolo de um conjunto finito de smbolos. A computacao e realizada
passo a passo ate o seu termino de acordo com a definicao do algoritmo A, ou seja, o seu
conjunto de instrucoes.
A definicao de A e formada a partir de um conjunto de regras ou instrucoes bastante
simples. A cada passo, o algoritmo A pode realizar uma das seguintes operacoes: ler um
smbolo da celula de memoria atual, escrever um smbolo sobre a celula atual, mover a
sua posicao de leitura para a celula da direita ou da esquerda, e atualizar o seu estado
interno de execucao. Portanto, a operacao de um algoritmo e algo estritamente local.
Apesar disso, uma combinacao adequada de regras pode levar a um comportamento global
extremamente complexo e imprevisvel.
O tempo de execucao do algoritmo e o n
umero de passos basicos realizados durante a
computacao. Embora a sua descricao seja finita, o uso da memoria e a alternancia entre os
estados internos do algoritmo pode levar a um tempo de execucao arbitrariamente grande.
Alem disso, como um algoritmo e um conjunto finito de regras bem definidas, ele pode
ser representado como uma palavra e servir de entrada para outros algoritmos.
A partir desses fatos basicos sobre algoritmos, vamos introduzir a formalizacao oferecida pelas maquinas de Turing (MT). Em uma maquina de Turing M , a memoria do
algoritmo e representada por meio de uma fita infinita para a direita. A maquina M pode
possuir diversas fitas de memoria. Mais precisamente, uma fita e uma sequencia infinita
de celulas, cada qual podendo conter um smbolo proveniente de um conjunto finito
chamado de alfabeto da maquina M . Cada fita e equipada com uma cabeca de leitura que
pode ler e escrever smbolos na fita uma celula por vez. A primeira fita de M e chamada
de fita de entrada e e onde se encontra a palavra de entrada no incio da computacao.
A u
ltima fita e chamada de fita de sada e armazena o resultado da computacao apos
o seu termino. As demais fitas sao chamadas fitas auxiliares e armazenam informacoes
utilizadas pela maquina M durante a sua computacao.
A maquina de Turing M possui um conjunto finito de estados que vamos denotar
por Q. A execucao da maquina de Turing e dividida em passos discretos, sendo que a
cada passo a maquina se encontra em um estado q Q especfico. Existem dois estados

especiais: q0 e qf . No incio de sua execucao, a maquina se encontra no estado inicial q0 .
O estado atual determina qual sera o proximo passo de M , que consiste em: (1) ler os
smbolos presentes nas celulas atuais de todas as fitas; (2) sobrescrever os smbolos atuais
com novos smbolos; (3) alterar o seu estado atual para um novo estado de Q; (4) mover
a cabeca de leitura de cada fita para a esquerda ou para direita. A computacao prossegue
atraves da alternancia entre o estado interno de M e o conte
udo das fitas. Imediatamente
apos entrar no estado final qf , a maquina termina a sua execucao e a sua sada e dada
pela palavra presente na fita de sada. Uma definicao um pouco mais formal das ideias
anteriores e apresentada a seguir.
Definic
ao 1.1. [Maquina de Turing]. Uma maquina de Turing M e descrita por uma
tupla (, Q, ) tal que:
(i) e o conjunto finito de smbolos (alfabeto) que as fitas de M podem conter. Assumimos que contem alguns smbolos especiais: um smbolo em branco ; um
smbolo inicial B; e os smbolos 0 e 1.
(ii) Q e o conjunto finito de estados da maquina M . Assumimos que Q contem os
estados especiais q0 e qf descritos anteriormente.
(iii) Uma funcao de transicao : Q k Q k {E, D}k , onde k e o n
umero de
fitas da maquina de Turing M .
Se a maquina esta no estado q Q, (1 , . . . , k ) sao os smbolos nas celulas atuais das
fitas de M e (q, (1 , . . . , k )) = (q 0 , (10 , . . . , k0 ), z), onde z {E, D}k , entao no proximo
passo os smbolos i serao alterados para i0 nas k fitas de M , a maquina passara para o
estado q 0 e a i-esima cabeca de leitura vai se mover para a esquerda ou para a direita de
acordo com o valor de zi . Se uma cabeca de leitura que estiver na celula mais extrema à
esquerda de sua fita tentar se mover para a esquerda, ela permanecera na mesma posicao
da fita.
Todas as fitas com excecao da primeira possuem a celula mais a esquerda inicializada
com o smbolo B e todas as outras celulas com o smbolo em branco . A fita de entrada
possui inicialmente o smbolo B, seguido da palavra finita de entrada x e em todas as
outras celulas. Todas as cabecas de leitura se posicionam inicialmente na primeira celula
de cada fita. O estado inicial da maquina e q0 . Cada passo da computacao e realizado
atraves da funcao de transicao , como descrito anteriormente. Se a maquina atingir o
estado qf , nenhum passo adicional e executado. Indicaremos por M (x) a sada da maquina de Turing M com entrada x, ou seja, M(x) e o conte
udo da fita de sada apos M
1.6. Maquinas de Turing
atingir o estado qf (desprezamos os infinitos smbolos à direita da palavra de sada).

Em complexidade computacional estamos interessados apenas em maquinas que terminam
a sua computacao em todas as entradas possveis.
Se M e uma maquina de Turing que produz apenas sadas binarias, entao denotaremos a
linguagem que M decide por L(M ) = {x ? : M (x) = 1}.
Embora o formalismo matematico seja fundamental para expressarmos provas de impossibilidade em complexidade computacional, na maioria das vezes nao precisaremos nos
concentrar em detalhes tecnicos do funcionamento das maquinas de Turing. O fato de
que muitos resultados sao independentes do modelo computacional em consideracao e um
importante aspecto da teoria de complexidade computacional.
Apresentamos a seguir um exemplo de maquina de Turing. Diversos outros exemplos
podem ser encontrados em Sipser [103].
Exemplo 1.2. [Problema dos Palndromos]. Considere a linguagem PALIN = {w
{0, 1}? : w e um palndromo }. Vamos construir uma maquina de Turing MP tal que
L(MP ) = PALIN. A maquina MP possuira uma fita de entrada, uma fita auxiliar e uma
fita de sada. Seu alfabeto sera composto por {, B, 0, 1}. Ela opera da seguinte maneira:
1) Copia a entrada para a fita auxiliar. A cabeca de leitura da fita auxiliar permanece
a direita da palavra copiada.
2) Move a cabeca de leitura da fita de entrada para o incio da fita.
3) Move a cabeca de leitura da fita de entrada para a direita enquanto move a cabeca de
leitura da fita auxiliar para a esquerda. Se em algum momento os valores nas duas fitas
sao diferentes, MP termina sua computacao e escreve 0 na fita de sada.
4) Quando MP esgota a fita de entrada (lendo nesta fita), MP escreve 1 na fita de
sada e termina sua computacao.
imediato a partir da construcao de MP que x L(MP ) se e somente se x e um palnE
dromo, ou seja, L(MP ) = PALIN.
Como discutido anterioremente, um aspecto importante dos algoritmos e em particular
das maquinas de Turing e a possibilidade de representa-los por meio de palavras. Como
a funcao de transicao de uma maquina de Turing caracteriza todo o seu comportamento,
facil desenvolver uma representacao
ela sera utilizada para a codificacao da maquina. E
que satisfaca os seguintes requisitos:
(i) Toda palavra em {0, 1}? representa alguma maquina de Turing.
10
(ii) Toda maquina de Turing (vista como um objeto matematico) e representada por
infinitas palavras.
Finalmente, observamos que os programas escritos em linguagens de programacao
modernas podem ser eficientemente simulados por maquinas de Turing (veja a secao de
referencias adicionais no fim do captulo). Por isso, em termos de poder computacional,
temos a equivalencia Algoritmos = Maquinas de Turing = Programas de Computador.
1.7
Efici
encia dos Algoritmos
Para estudar a dificuldade dos problemas computacionais e preciso quantificar a nocao

de eficiencia de um algoritmo. Diversas medidas de complexidade podem ser utilizados
para isso, como o n
umero de passos basicos realizados pelo algoritmo ou a memoria total
utilizada durante a computacao.
Fixada uma medida de complexidade conveniente, para comparar o desempenho de
dois algoritmos e interessante desprezar detalhes tecnicos irrelevantes e dar maior importancia para a ideia fundamental por tras de cada algoritmo. Por isso, o desempenho de
dois algoritmos e comparado atraves do crescimento da funcao de complexidade quando
instancias cada vez maiores sao utilizadas na entrada.
Pode-se tambem considerar uma distribuicao de probabilidade no conjunto de instancias de cada tamanho para o calculo da complexidade final do algoritmo. Por ser mais
facil trabalhar sem esse parametro adicional, geralmente a analise de pior caso e adotada.
Isso significa que a complexidade do algoritmo para instancias de tamanho n e definida
como sendo o maior valor adquirido pela medida de complexidade adotada em instancias
de tamanho n.
Nesta dissertacao utilizaremos como principal medida de complexidade o n
umero de
passos basicos utilizados por um algoritmo. Alem disso, o problema P vs NP e a maioria
dos resultados importantes em complexidade computacional sao baseados na analise de
pior caso. Isso torna o estudo teorico de diversos problemas viavel e conveniente.
Definic
ao 1.3. [Funcao Computada por uma Maquina de Turing]. Sejam f : {0, 1}?
{0, 1}? uma funcao e M uma maquina de Turing. Dizemos que M computa a funcao f
se para todo x {0, 1}? , sempre que M e inicializada com entrada x temos M (x) = f (x).
Definic
ao 1.4. [Complexidade de Tempo]. A complexidade de tempo exata de uma maquina de Turing M e dada pela funcao tM : {0, 1}? N, de forma que quando inicializada com x em sua fita de entrada, M termina sua computacao em exatamente
tM (x) passos. A complexidade de tempo de M e dada pela funcao TM : N N tal
que TM (n) = max{tM (x) : x {0, 1}n }.
1.8. Um Exemplo de Limitante Inferior
11
facil perceber que a maquina de Turing apresentada na secao anterior computa

E
PALIN em tempo O(n), ou seja, TMP (n) e O(n).
De forma analoga, podemos definir a complexidade de espaco de uma maquina de
Turing.
Definic
ao 1.5. [Complexidade de Espaco]. A complexidade de espaco exata de uma
maquina de Turing M e dada pela funcao sM : {0, 1}? N, de forma que quando
inicializada com x em sua fita de entrada, M acessa exatamente sM (x) celulas distintas
entre todas as suas fitas. A complexidade de espaco de M e dada pela funcao SM : N N
tal que SM (n) = max{sM (x) : x {0, 1}n }.
1.8
Um Exemplo de Limitante Inferior
Os pesquisadores que estudam complexidade estao interessados em determinar a complexidade computacional de cada problema. Embora essa seja uma tarefa bastante difcil
para a maioria dos problemas computacionais, e possvel caracterizar precisamente a complexidade de algumas tarefas simples.
Nesta secao vamos considerar apenas maquinas de Turing com uma u
nica fita. Como
vamos trabalhar apenas com linguagens, nao ha necessidade de ter uma fita separada para
sada. Por conveniencia, vamos assumir que existem dois estados especiais qaceitar e qrejeitar
no conjunto de estados Q de cada maquina de Turing. Uma maquina M aceita a palavra
x se em algum passo de sua computacao ela entra no estado qaceitar . Analogamente, M
rejeita x caso seja colocada no estado qrejeitar durante sua computacao. Uma vez nesses
estados, M termina sua computacao imediatamente.
Considere novamente a linguagem PALIN = {x {0, 1}? : x e um palndromo }. E

facil desenvolver uma maquina de Turing M de fita u
nica capaz de decid-la em tempo
2
O(n ). Basicamente, M cruza a fita por no maximo n vezes enquanto checa se o smbolo
mais a esquerda ainda nao verificado e o mesmo que o smbolo mais a direita ainda
nao verificado. Como em cada cruzamento a maquina percorre no maximo n celulas, a
complexidade de tempo total e O(n2 ).
Como provar que esse zig-zag e essencialmente a melhor maneira de resolver esse
problema utilizando maquinas de Turing com uma u
nica fita? Pode parecer intuitivo que
2
cerca de n passos sejam necessarios, mas precisamos encontrar uma prova formal para esse
fato. Para isso, utilizaremos um conceito importante da teoria de informacao chamado
complexidade de Kolmogorov. Intuitivamente, a complexidade de Kolmogorov de uma
sequencia de bits e o tamanho do menor programa capaz de imprimir tal sequencia.
Mostraremos a seguir que qualquer maquina de Turing de fita u
nica capaz de decidir
2
PALIN precisa de (n ) passos para completar a sua computacao.
12
Definic
ao 1.6. [Complexidade de Kolmogorov]. Seja = (M1 , M2 , . . .) uma codificacao
das maquinas de Turing no alfabeto {0, 1} a partir das respectivas funcoes de transicao.
Para cada palavra x {0, 1}, a sua complexidade de Kolmogorov em relacao a e:
K (x) = min{|Mj | : Mj () = x}.
Lema 1.7. [Palavras Incompressveis]. Para todo n N existe uma palavra x de tamanho
n tal que K (x) n.
Demonstracao. Existem 2n palavras de tamanho n e apenas 2n 1 palavras de tamanho
menor ou igual a n1. Como cada maquina de Turing representa no maximo uma palavra,
deve existir alguma palavra de tamanho n que nao pode ser representada no sentido da
complexidade de Kolmogorov por maquinas de Turing de tamanho menor que n.
O lema anterior prova que existem palavras incompressveis. Vamos agora descrever a
ideia utilizada na prova do limitante inferior (n2 ) para PALIN para maquinas de Turing
com uma u
nica fita. Em primeiro lugar, vamos mostrar que o tempo de execucao de
qualquer algoritmo decidindo PALIN pode ser usado para provar um limitante superior na
complexidade de Kolmogorov das palavras do alfabeto {0, 1}? . Depois disso mostraremos
que, caso o algoritmo seja rapido demais (utilize o(n2 ) passos), entao teremos uma violacao
do fato de que existem palavras incompressveis. Esse argumento e conhecido como metodo
da incompressibilidade. A seguir apresentamos a prova formal desse resultado.
Teorema 1.8. Seja M uma maquina de Turing de fita u
nica que decide PALIN. Entao
2
a complexidade de tempo de M e (n ).
Demonstracao. Considere a computacao de M com uma entrada w. Dizemos que em um
determinado passo da computacao de M ocorre um cruzamento entre as celulas i e i + 1
da fita com o estado q se: (i) antes desse passo a cabeca de leitura de M se encontra
na celula i ou na celula i + 1 da fita; (ii ) apos esse passo a cabeca de leitura de M
tambem se encontra na celula i ou na celula i + 1 da fita; (iii) o estado de M apos esse
passo e q. A sequencia de cruzamentos de M com entrada w entre as celulas i e i + 1
da fita sera denotada por Si (M, w) = (q1 , . . . , qm ), de forma que todos os cruzamentos
existentes aparecem em Si (M, w) e os mesmos estao ordenados de acordo com o n
umero
do passo da computacao no momento do cruzamento. Observe que, dada uma sequencia
de cruzamentos, cruzamentos de n
umero mpar sao oriundos de passos da computacao de
M que entram na posicao i + 1 da fita a partir da posicao i, e cruzamentos de n
umero
par sao oriundos de passos da computacao de M que entram na posicao i da fita a partir
da posicao i + 1.
Do ponto de vista das primeiras i posicoes da fita, tudo o que importa e o processamento que ocorre dentro dessas posicoes e a sequencia de cruzamentos de n
umero par
1.8. Um Exemplo de Limitante Inferior
13
em Si (M, w). Isso significa que, independentemente do que aconteca nas outras posicoes
localizadas à direita da celula i, desde que a sequencia de cruzamentos de n
umero par
seja a mesma teremos os mesmos smbolos escritos nas primeiras i posicoes de memoria
ao termino da computacao. O mesmo ocorre com as posicoes da fita localizadas à direita
da celula i em relacao aos cruzamentos de n
umero mpar em Si (M, w). Esse resultado
ilustra o fato de que a computacao e um fenomeno local.
Seja agora w = x0n xR , onde xR denota o reverso de x (x escrito ao contrario) e x e
uma palavra incompressvel de tamanho n (veja o lema anterior). Lembre-se que tM (w)
e o n
umero de passos de M com entrada w. Deve existir uma posicao i da fita em um
dos locais inicialmente ocupados pela parte da entrada correspondente a 0n com n
umero
de cruzamentos m entre as celulas i e i + 1 satisfazendo m tM (w)/n. Isso ocorre pois,
caso contrario, teramos uma violacao do n
umero total de passos tM (w) de M . Suponha
que a sequencia de cruzamentos entre essas celulas seja Si (M, w) = (q1 , . . . , qm ).
Vamos agora provar que, em relacao a` maquina M , a tupla (i, n, Si (M, w)) identifica de
forma u
nica a palavra original x utilizada na construcao de w. Com o intuito de obtermos
uma contradicao, suponha que exista uma palavra distinta w0 = y0n y R de tamanho 3n
com a mesma tupla anterior. Considere agora o processamento de M com a entrada
facil perceber que essa entrada produz a mesma sequencia de cruzamentos
x0n y R . E
entre as celulas i e i + 1 que as palavras w e w0 . Por isso, durante a computacao de M
com essa nova entrada, M se comporta nas primeiras i posicoes da fita como se estivesse
processando a palavra w, e nas outras posicoes superiores como se estivesse processando
a palavra w0 . Como w e w0 sao palndromos, as duas palavras sao aceitas por M . Isso
implica que, independentemente do local onde ocorra o u
ltimo passo de sua computacao,
n R
a palavra x0 y tambem sera aceita por M . Como M decide PALIN e x0n y R nao e um
palndromo, obtemos uma contradicao.
Provaremos a seguir que existe um maquina de Turing M 0 que, dada a tupla (i, n, Si (M, w)),
imprime a palavra x. Essa maquina computa da seguinte maneira:
1) Gera em ordem lexicografica todas as palavras de tamanho 3n na forma z0n z R .
2) Simula a maquina M em cada uma dessas entradas.
3) Se ao termino de alguma simulacao a sequencia de cruzamentos entre as celulas i e
i + 1 for igual a Si (M, w), a maquina M 0 imprime a palavra z usada na simulacao atual
e termina seu processamento.
Como x e a u
nica palavra compatvel com a tupla de entrada, o algoritmo anterior
imprime x ao termino de sua execucao. Podemos adicionar a tupla (i, n, Si (M, w)) a`
memoria interna de M 0 para obtermos uma maquina Mx tal que Mx () = x.
Para todo x, qual o tamanho da palavra que codifica a maquina Mx ? Claramente,
14
isso depende apenas do tamanho da tupla ligada a x e de uma constante cM 0 relacionada

aos detalhes de implementacao da maquina M 0 . Na tupla de x, temos que os valores i e n
podem ser representados por log n bits. Por outro lado, Si (M, w) pode ser codificado em
no maximo mcM tM (w)cM /n bits, onde a constante cM depende apenas da maquina de
Turing M . Como x e uma palavra incompressvel, isso prova que:
n K (x) cM tM (w)/n + 2 log n + cM 0 .
Reescrevendo essa desigualdade, obtemos:
tM (w) (n2 2n log n ncM 0 )/cM = (n2 ).
O fato de que |w| = 3n nao altera o resultado assintotico e por isso TM (n) = (n2 ), como
queramos demonstrar.
Lembre-se que a linguagem PALIN pode ser decidida por maquinas de Turing com
varias fitas em tempo O(n). Portanto, esse teorema mostra que maquinas com varias
fitas sao mais poderosas do que maquinas de fita u
nica.
Embora o metodo da incompressibilidade utilize um argumento muito elegante para
provar limitantes inferiores, ele e muito engenhoso e nao parece ser forte o suficiente
para provar cotas inferiores exponenciais, por exemplo. Veremos na secao 3.6 que existem
argumentos que, quando aplicaveis, sao capazes de provar limitantes inferiores muito mais
fortes.
O resultado provado nesta secao e fortemente dependente das sutilezas do modelo computacional escolhido (maquinas de Turing com uma u
nica fita). Ele foi apresentado para
ilustrar a grande diferenca entre a prova de um limitante superior (atraves do desenvolvimento de um algoritmo) e a prova de um limitante inferior (atraves de uma demonstracao
matematica). Notamos que, apesar de resultados como esse serem interessantes, os pesquisadores em complexidade computacional estao mais interessados em provar resultados
que nao dependem de detalhes do modelo computacional em consideracao.
1.9
Refer
encias Adicionais
Uma excelente introducao à teoria da computacao e o livro de Sipser [103]. Para um

estudo mais avancado da teoria de computabilidade, recomendamos a leitura de Rogers
[93] e Odifreddi [84, 85]. Diversos artigos classicos em computabilidade estao reunidos em
Davis [31]. O livro de Savage [95] discute diversos modelos computacionais estudados em
computacao. O livro de Carnielli e Epstein [19] e uma otima referenca em portugues para
leitores interessados na relacao entre computabilidade e os fundamentos da matematica.
A definicao de maquinas de Turing apresentada neste captulo e baseada no livro de
Arora e Barak [7]. Uma possvel excecao para a eficiencia universal das maquinas de Turing
1.9. Referencias Adicionais
15
em relacao a outros modelos computacionais e o desenvolvimento de um computador

quantico. Entretando, ainda nao temos certeza de que o modelo teorico por tras dessas
maquinas e fisicamente realizavel. Recomendamos os livros de Hirvensalo [57] e Kaye et
al. [67] para uma introducao ao tema.
O compendio de matematica editado por Gowers et al. [48] contem um excelente artigo
de Goldreich que discute os principais problemas e desafios enfrentados em complexidade
computacional. O artigo de Fortnow e Homer [42] da uma retrospectiva dos desenvolvimentos em complexidade. Outro artigo no mesmo estilo e Impagliazzo [62]. Uma discussao
fascinante sobre a relacao entre complexidade computacional e matematica pode ser encontrada em Wigderson [109]. Um livro classico sobre complexidade computacional e
Papadimitriou [88]. Outros livros mais recentes sao Arora e Barak [7] e Goldreich [47].
Para uma discussao informal sobre o estado atual do problema P vs NP, veja o artigo
recente de Fortnow [41]. A historia do problema esta contada em Sipser [102] e a sua
importacia e resumida em Cook [24]. Veja a secao final dos outros captulos do texto para
referencias tecnicas sobre o problema.
A complexidade de Kolmogorov e o metodo da incompressibilidade sao discutidos no
livro de Li e Vitanyi [75]. O teorema 1.8 foi provado no artigo de Hennie [55]. Uma
extensao das ideias utilizadas na demonstracao desse resultado pode ser obtida em Maass
[77].
Captulo 2
Introdu
c
ao ao Problema P vs NP
There is the problem, seek the solution.
You can find it through pure thought.
David Hilbert.
Neste captulo abordamos o principal problema em aberto da teoria de complexidade computacional: a relacao 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 solucoes e
essencialmente a melhor alternativa algortmica possvel. Apresentamos diversas formulacoes equivalentes para esse problema, alem de discutirmos sua
importancia e os principais metodos empregados na tentativa de resolve-lo.
2.1
Introduc
ao
A mera existencia de um programa de computador capaz de resolver um problema

nao significa que sua solucao por meios computacionais seja de fato viavel. Considere,
por exemplo, a tarefa de encontrar o menor caminho a ser percorrido de carro para viajar
entre duas cidades. A solucao imediata de procurar pelo caminho de menor distancia
entre todos os caminhos possveis pode resultar em uma busca extremamente demorada.
Para visualizar isso, basta levar em conta que as duas cidades podem estar localizadas nos
dois extremos de um continente. A quantidade de caminhos possvel se torna tao grande
que, mesmo apos varias horas de execucao, pode ser que nenhum computador moderno
encontre o trajeto otimo. Por isso, embora o algoritmo proposto para essa tarefa seja
correto, a busca exaustiva inviabiliza completamente a solucao do problema. Veremos
17
18
Captulo 2. Introducao ao Problema P vs NP
na proxima secao que o problema do caminho mnimo possui uma solucao muito mais
eficiente. A classe de problemas que admitem algoritmos eficientes e denotada por P.
Em meados da decada de sessenta, A. Cobham [22] e J. Edmonds [34] estavam interessados em muitas questoes desse tipo. Em particular, Edmonds foi capaz de provar que a
busca exaustiva nao e a melhor solucao computacional para muitos problemas de interesse
pratico. Para conseguir isso, e preciso explorar de forma inteligente a estrutura intrnseca
de cada problema. Segundo Edmonds, um algoritmo capaz de tirar proveito das sutilezas
do problema computacional em consideracao poderia ser considerado um bom algoritmo.
Apesar de ter mostrado que isso e possvel para muitas tarefas, ele e outros pesquisadores
da epoca nao foram capazes de encontrar solucoes mais elegantes que a busca exaustiva
para muitos outros problemas importantes.
O principal problema da busca exaustiva e que sua implementacao requer um n
umero
de passos computacionais proporcional ao n
umero de possibilidades no espaco de busca,
o que e em geral uma funcao de crescimento exponencial no tamanho das instancias do
problema. Com a descoberta de novos algoritmos, ficou claro que a existencia de um algoritmo de complexidade exponencial para um problema nao significava que a complexidade
real do problema era exponencial. Cobham e Edmonds sugeriram que um algoritmo e eficiente quando seu n
umero de passos e limitado por uma funcao algebrica, ou seja, por
um polinomio. Como essa definicao apresenta diversas propriedades interessantes e a experiencia nos mostra que algoritmos polinomiais sao computacionalmente viaveis, ela se
tornou amplamente aceita.
Os pesquisadores logo perceberam que diversos problemas computacionais difceis possuem uma propriedade muito especial: dada uma resposta para uma instancia do problema, e possvel verificar de modo eficiente se ela e de fato uma das solucoes procuradas.
A classe de problemas com solucoes que podem ser verificadas de modo eficiente e denotada por NP.
Lembre que P representa a classe de problemas com solucoes que podem ser encontradas de modo eficiente. Qual a relacao entre as classes P e NP? Em outras palavras,
se podemos verificar a solucao de um problema em tempo polinomial, entao tambem
podemos encontrar a solucao em tempo polinomial?
facil verificar quando
Vejamos, atraves de um exemplo simples, o que isso significa. E
uma sequencia de n
umeros e uma solucao para um quebra-cabecas Sudoku1 . Portanto,
Sudoku e um problema pertencente a` classe NP2 . No entanto, existe algum modo inteligente de encontrar rapidamente a solucao para um jogo de Sudoku? Ou seja, Sudoku
pertence a` classe P?
1
A descric
ao do jogo Sudoku pode ser obtida em http://pt.wikipedia.org/wiki/Sudoku.
Para essa afirmac
ao fazer sentido, estamos considerando que os tabuleiros de Sudoku podem ser
arbitrariamente grandes.
2
2.1. Introducao
19
O problema P vs NP procura estabelecer essa questao para todos os problemas com

solucoes que podem ser verificadas de forma eficiente. Se as classes P e NP forem identicas, entao as solucoes de Sudoku, e de milhares de outros problemas computacionais
importantes, podem ser encontradas de forma eficiente. Nao sera necessaria nenhuma criatividade adicional para resolver esses problemas. Descobrir uma solucao sera tao simples
quanto verificar uma solucao.
A classe NP possui muitos problemas relevantes. Considere, por exemplo, o conjunto
de teorias cientficas capazes de explicar um certo fenomeno. Em geral, temos uma ideia
razoavel do que pode ser considerado uma teoria. Alem disso, usualmente e possvel
estabelecer uma medida de sucesso para a compatibilidade de cada teoria com os dados
cientficos disponveis, sendo que esse teste pode ser feito de modo eficiente (uma maneira
de fazer isso seria comparar as predicoes da teoria com os dados experimentais). Portanto,
dado um nvel de precisao desejado, e possvel verificar de forma eficiente se uma teoria
e adequada para explicar um determinado fenomeno. Por isso, esse problema pertence
a` classe NP. Se P = NP, entao tambem podemos encontrar rapidamente as melhores
teorias capazes de explicar os dados cientficos disponveis. Seria possvel, por exemplo,
encontrar uma teoria para explicar com precisao os dados coletados atraves da colisao de
partculas em altas energias no novo acelerador LHC. Nao so isso, como veremos na secao
4.1, seria viavel encontrar a teoria com a menor descricao possvel satisfazendo as mesmas
propriedades. Muitas vezes, a teoria mais simples possvel e a teoria correta.
Devido a essa e diversas outras implicacoes fascinantes, muitos pesquisadores acreditam que P 6= NP. Entretanto, ainda nao sabemos provar esse fato. Por isso, por mais
improvavel que possa parecer, nao podemos descartar a possibilidade de que P = NP.
Alem do mais, ja fomos surpreendidos diversas vezes com ideias brilhantes capazes de
superar os melhores algoritmos existentes ate entao.
Para provarmos definitivamente que P 6= NP, sera necessario mostrar que existe um
problema em NP muito especial. Especificamente, sera preciso demonstrar que nenhuma
ideia pode ser usada para resolver esse problema de modo eficiente. De modo surpreendente, se essas classes forem realmente distintas, ja sabemos quais sao os problemas
candidatos (veja a secao 2.5).
Que tipo de matematica podemos utilizar para separar essas duas classes de problemas
computacionais? Ainda nao sabemos responder essa questao, mas somos capazes de provar
que diversos metodos matematicos poderosos nao sao suficientes. Um exemplo importante
de resultado nesse sentido sera apresentado no captulo 5. Na proxima secao apresentamos
o enunciado formal do problema P vs NP.
20
2.2
Definic
ao
A descricao apresentada anteriormente para o problema P vs NP corresponde a` sua

versao de busca. No entanto, o estudo de problemas desse tipo pode ser reduzido ao
estudo de problemas de decisao (i.e., problemas de pertinencia em linguagens). Por isso,
vamos considerar como enunciado formal do problema P vs NP a sua versao de decisao.
Por ser mais simples, essa abordagem e amplamente utilizada na literatura. Na secao 2.3
mostraremos que as duas formulacoes sao de fato equivalentes (versao de busca vs versao
de decisao).
Definic
ao 2.1. [Classe de Complexidade DTIME]. Seja T : N N uma funcao. Uma
linguagem L {0, 1}? pertence à classe DTIME(T (n)) se existe uma maquina de Turing
M que decide L em O(T (n)) passos.
Observe que estamos interessados apenas no comportamento assintotico da funcao de
complexidade. Em outras palavras, os termos aditivos inferiores e as constantes multiplicativas nao sao relevantes para a teoria de complexidade computacional. Isso torna
os resultados muito mais simples e elegantes, alem de ser uma convencao que pode ser
justificada pelo seguinte teorema.
Teorema 2.2. [Teorema do Speedup Linear]. Sejam M uma maquina de Turing, TM (n)
sua funcao de complexidade de tempo e suponha que M decida a linguagem L. Para
todo n
umero real > 0, existe uma maquina de Turing M que decide L em tempo
TM (n) TM (n) + n + 2.
Demonstracao. Aumentamos o alfabeto de M de forma que uma sequencia de smbolos
do alfabeto original de M possa ser representado por um u
nico smbolo em M . Com
isso, a maquina de Turing M pode simular diversos passos de M em um u
nico passo. Os
termos adicionais que aparecem na expressao de TM (n) resultam do processamento inicial
necessario para converter a palavra de entrada para os novos smbolos. A demonstracao
completa desse resultado pode ser obtida no livro de Papadimitriou [88].
Vamos agora definir a classe de complexidade que abriga as linguagens que podem ser
decididas eficientemente.
Definic
ao 2.3. [Classe de Complexidade P].
S
P = k1 DTIME(nk ).
O proximo exemplo exibe um algoritmo eficiente para o problema discutido no incio
da secao anterior.
2.2. Definicao
21
Exemplo 2.4. [Problema do Caminho Mnimo]. Esse problema pode ser modelado atraves
de um grafo com peso nas arestas. Seja G = (V, E, p) um grafo, onde V e um conjunto de
vertices (cidades), E e um conjunto de pares nao-ordenados de vertices (cidades vizinhas)
e p : E R+ e o peso de cada aresta (distancia entre as cidades vizinhas). Se C =
(v1 , . . . , vn ) e um caminho no grafo G, a distancia de C e dada pela soma do peso das
arestas vi vi+1 E, onde 1 i n 1. Dados dois vertices s e t em G, nosso algoritmo
deve determinar qual e o caminho entre s e t com a menor distancia total. Vamos a seguir
descrever um algoritmo A que resolve de forma eficiente esse problema.
Adotamos as seguintes convencoes. Fixe uma ordem qualquer nas arestas de G. Vamos
denotar por Ek o conjunto que contem as k primeiras arestas segundo essa ordem. Seja
Gk = (V, Ek , p|Ek ) o subgrafo ponderado de G que contem todos os vertices originais de G e
apenas as k primeiras arestas segundo essa ordem. O algoritmo A resolvera um problema
mais geral que o proposto. Na k-esima etapa, ira encontrar o menor caminho entre todos
os pares de vertices do grafo Gk . O caso base G0 e trivial. Assuma que A tenha executado
por k etapas e seja Ck (u, v) o menor caminho encontrado entre os vertices u e v no grafo
Gk . A distancia total do caminho Ck (u, v) sera denotada por dk (u, v). Como encontrar
os melhores caminhos no grafo Gk+1 ?
Em primeiro lugar, se a nova aresta ek+1 = {w1 , w2 } e tal que p(ek+1 ) dk (w1 , w2 ),
entao os melhores caminhos e as melhores distancias nao sao alterados. Caso contr
ario,
para todos os pares de vertices ja sabemos qual e o menor caminho entre eles em Gk+1 que
nao utiliza a nova aresta. Sejam v1 e v2 dois vertices de G. Temos duas possibilidades para
cada caminho otimo em Gk+1 . Ou ele e igual ao caminho anterior, ou utiliza a nova aresta.
Como qualquer aresta so aparece uma u
nica vez em um caminho otimo, basta A comparar
dk (v1 , v2 ) com dk (v1 , w1 ) + p(ek+1 ) + dk (w2 , v2 ) e com dk (v1 , w2 ) + p(ek+1 ) + dk (w1 , v2 ) para
determinar Ck+1 (v1 , v2 ) e dk+1 (v1 , v2 ). Isso completa a descricao do algoritmo A.
O leitor pode verificar facilmente que esse algoritmo utiliza um n
umero de passos
polinomial em |E| + |V |. Considere agora a versao de decisao do problema anterior:
DISTMIN = {hG, s, t, ki : G e um grafo ponderado e dG (s, t) k}.
Podemos utilizar o algoritmo anterior para determinar em tempo polinomial o menor
caminho entre os vertices s e t e comparar sua distancia com o valor k. Por isso, temos
que DISTMIN P.
Apresentamos a seguir a definicao da classe NP. Uma definicao alternativa e discutida
na secao 2.4.
Definic
ao 2.5. [Classe de Complexidade NP].
Uma linguagem L {0, 1}? pertence a classe NP se existe um polinomio p(.) : N N e
uma maquina de Turing V de tempo polinomial tal que para todo x {0, 1}? :
22
x L w {0, 1}p(|x|) tal que V (x, w) = 1.

Se x L, w {0, 1}p(|x|) e V (x, w) = 1, dizemos que w e um certificado para x em relacao
a linguagem L e a maquina V . Alem disso, dizemos que V e um verificador eficiente para
a linguagem L.
Observe que a exigencia na definicao da classe NP de que o tamanho dos certificados
seja exatamente p(n) para entradas de tamanho n nao e essencial. Basta que algum
polinomio limite o tamanho dos certificados, uma vez que sempre podemos completalos ate que atinjam o tamanho desejado. Vale reforcar que se L NP, entao L e uma
linguagem decidvel (x L se e somente se V (x, w) = 1 para alguma palavra w de
tamanho p(|x|)).
Na classe NP residem as linguagems que possuem certificados sucintos e eficientemente
verificaveis para a presenca de uma palavra na linguagem. Vejamos um exemplo.
Exemplo 2.6. [COMPOSTOS NP]. Considere a seguinte linguagem:
COMPOSTOS = {hni : k N, 1 < k < n e k divide n}.
Como a existencia de um divisor nao trivial de n serve como certificado canonico para
hni COMPOSTOS e a relacao de divisibilidade pode ser verificada em tempo polinomial, temos que COMPOSTOS NP. Recentemente, um algoritmo eficiente conhecido
como AKS foi encontrado para esse problema, ou seja, na verdade temos tambem que
COMPOSTOS P. Veja a secao de referencias deste captulo para mais detalhes.
A versao de busca do problema P vs NP pergunta se encontrar uma solucao e mais
difcil do que verificar as solucoes. Por outro lado, a versao de decisao desse problema
pergunta se verificar uma afirmacao por conta propria e mais difcil do que checar a
validade de uma prova eficiente. O exemplo anterior mostra que e facil convencer alguem
de que um n
umero e composto atraves de um certificado. Neste caso, porem, tambem e
possvel verificar essa afirmacao de forma eficiente utilizando o algoritmo AKS. E quanto
ao caso geral? A principal questao em aberto da teoria de complexidade computacional
pode ser enunciada da seguinte maneira.
Quest
ao em Aberto 2.7. P = NP ?
Na secao 2.7 apresentamos as principais abordagens utilizadas ate agora na tentativa
de resolver esse problema.
Suponha, por um momento, que nao tivessemos conhecimento sobre o algoritmo AKS.
Como convencer alguem rapidamente de que um n
umero nao e composto, ou seja, e
primo? Existe alguma prova sucinta e eficiente para a propriedade de ser n
umero primo?
A classe de complexidade coNP abriga as linguagens para as quais podemos apresentar
um certificado eficiente de que uma dada palavra nao esta na linguagem.
2.2. Definicao
23
Definic
ao 2.8. [Classe de Complexidade coNP].
coNP = { L : L NP }.
Definic
ao 2.9. De forma geral, se R e uma classe de complexidade, definimos coR =
{ L : L R}.
Observe que a classe coNP nao e o complemento do conjunto NP. Por definicao, se
uma linguagem L esta em coNP, entao podemos verificar eficientemente atraves de um
certificado que uma certa palavra nao pertence a` linguagem L.
Por exemplo, enquanto e facil provar que um dado sistema de equacoes quadraticas
possui solucao (basta apresentar a solucao), como convencer alguem de que esse sistema
nao e satisfatvel? Existe algum certificado eficiente que possa ser usado para comprovar
a ausencia de solucoes? No caso geral, temos o seguinte problema.
Quest
ao em Aberto 2.10. NP = coNP ?
Esse problema tambem e muito importante, e sua solucao ampliara nosso entendimento
sobre a capacidade das provas eficientes. Alem disso, temos a seguinte relacao entre as
conjecturas anteriores.
Definic
ao 2.11. Seja R uma classe de complexidade. Dizemos que R e fechada por
complementacao de linguagens se, para toda linguagem L R, temos L R.
Lema 2.12. Se NP 6= coNP , entao P 6= NP.
Demonstracao. Em primeiro lugar, observe que NP = coNP se e somente se NP e fechada
por complementacao de linguagens (isso vale em geral para qualquer classe de complexidade). Portanto, segue pela hipotese do lema que NP nao possui essa propriedade. No
entanto, invertendo os estados de aceitacao e rejeicao de uma maquina determinstica,
temos que P e uma classe fechada por complementacao de linguagens. Isso prova que
P 6= NP.
Veremos mais alguns resultados relacionando as classes NP e coNP na secao 4.4. Veja
a secao de referencias adicionais deste captulo para saber mais sobre a questao NP vs
coNP.
Temos ainda outro relacionamento basico entre as classes discutidas anteriormente.
Lema 2.13. P NP coNP.
Demonstracao. Como P e uma classe fechada por complementacao de linguagens, basta
provar que P NP. Seja M uma maquina de Turing polinomial que decide L. Considere
imediato que
o verificador V que aceita a entrada hx, wi se e somente se M (x) = 1. E
V e um verificador eficiente. Tomando, por exemplo, o polinomio p(n) = n, temos que
x L w {0, 1}p(|x|) tal que V (x, w) = 1. Isso prova que L NP.
24
Suponha agora que exista uma linguagem L que admite certificados eficientemente
verificaveis tanto para presenca de palavras na linguagem quanto para ausencia de palavras. Em outras palavras, L NP coNP. Podemos concluir, nesse caso, que L pode ser
decidida em tempo polinomial?
Quest
ao em Aberto 2.14. P = NP coNP ?
Similarmente, e possvel demonstrar que se esse resultado for falso entao P 6= NP.
Vimos nesta secao que outras duas perguntas interessantes surgem naturalmente a
partir do enunciado do problema P vs NP. A solucao de qualquer um desses problemas
sera um avanco importante para a teoria de complexidade computacional.
2.3
Decis
ao vs Busca
Nesta secao vamos demonstrar que a versao de busca do problema P vs NP discutida

na secao inicial nao e mais difcil do que a versao de decisao definida na secao anterior. Em
primeiro lugar, descreveremos informalmente uma maneira de formalizar a versao de busca
do problema. Depois argumentaremos que as duas formulacoes sao de fato equivalentes.
Considere novamente o exemplo 2.4. A linguagem DISTMIN possui certificados eficientes muito simples: basta exibir um caminho de comprimento menor ou igual a k para
comprovar a presenca de uma palavra na linguagem. Colocado de outra forma, os certificados de NP podem ser visualizados como solucoes para uma dada instancia do problema.
Por isso, as linguagens em NP sao aquelas com solucoes eficientemente verificaveis. Por
outro lado, encontrar a solucao de uma instancia de um problema em NP e o mesmo que
obter um certificado em relacao a um verificador V .
claro que se P = NP para a versao de busca, entao temos P = NP para a versao
E
de decisao. Basta utilizar o algoritmo que encontra as solucoes (certificados) de modo
eficiente e descartar a solucao encontrada, uma vez que tudo que precisamos saber na
versao de decisao e se existe um certificado valido para a entrada ou nao. Por outro lado,
suponha que P = NP no sentido formal apresentado na secao anterior (versao de decisao).
Podemos encontrar solucoes (certificados) de modo eficiente?
Vamos obter o certificado procurado bit por bit. Primeiro, mostramos que o problema
de verificar se uma palavra e o incio de um certificado pertence a` classe NP. A hipotese
de que P = NP fornece um algoritmo eficiente para essa tarefa. Finalmente, usamos
esse algoritmo para buscar de modo eficiente algum certificado. Partimos agora para a
descricao formal dessas ideias.
Teorema 2.15. Suponha que P = NP. Seja L NP e V um verificador eficiente para
L. Entao existe uma maquina de Turing M de tempo polinomial tal que para todo x L,
2.4. Uma Formulacao Alternativa
25
M imprime um certificado w para x (em relacao ao verificador V ). Em outras palavras,

se x L entao V (x, M (x)) = 1. Alem disso, M indica que nao ha certificado para x no
caso em que x
/ L.
Demonstracao. Seja p(.) : N N o polinomio que descreve o tamanho dos certificados
de L em relacao ao verificador V . Considere a seguinte linguagem:
L0 = {hx, w0 i : w00 tal que |w00 | = p(|x|) |w0 | e V (x, w0 w00 ) = 1}.
facil perceber que L0 NP, uma vez que a propria palavra w00 serve como certificado
E
para a entrada hx, w0 i. Mais ainda, note que x L se e somente se hx, i L0 .
Como temos por hipotese que P = NP, segue que L0 P. Seja M 0 uma maquina de
Turing de tempo polinomial que decide L0 . Vamos utiliza-la como subrotina para a construcao da maquina M do enunciado. Com entrada x, M computa da seguinte maneira:
1) Se M 0 (x, ) = 0, M declara que x
/ L.
2) Caso contrario, M encontra bit por bit um certificado w para a entrada x. Inicialmente,
w := .
3) Enquanto |w| < p(|x|): se M 0 (x, w0) = 1 entao w := w0, senao w := w1.
4) Imprime w e encerra sua execucao.
Como M faz no maximo p(|x|) + 1 chamadas a` maquina polinomial M 0 , o certificado
procurado e encontrado de modo eficiente, caso ele exista.
O argumento utilizado na demonstracao anterior e conhecido como metodo do prefixo.
Esse metodo sera u
til novamente na secao 4.6.
2.4
Uma Formula
c
ao Alternativa
A classe NP tambem pode ser definida atraves da introducao de um novo recurso

nas maquinas de Turing: a habilidade de realizar m
ultiplas escolhas durante os passos
de sua computacao. A u
nica diferenca entre uma maquina de Turing nao-determinstica
(MTND) e uma maquina usual (veja a definicao 1.1) e que a MTND possui duas funcoes
de transicao 0 e 1 , alem de um estado especial denotado por qaceitar . Durante cada
passo da computacao de uma MTND M , uma das duas funcoes de transicao e aplicada de
forma arbitraria. Dada uma entrada x, dizemos que M (x) = 1 se existe alguma sequencia
de aplicacao das funcoes de transicao 0 e 1 que faz M entrar no estado qaceitar . Caso
contrario, dizemos que M (x) = 0. Dizemos que uma MTND M decide a linguagem L
quando x L se e somente se M (x) = 1. Finalmente, dizemos que a MTND M termina
sua computacao em k passos com uma entrada x {0, 1}? se existe uma sequencia de
26
escolhas nao-determinsticas para aplicacao das funcoes de transicao de M em que o

n
umero de passos executados por M e k, e em nenhuma outra sequencia de escolhas M
executa por mais que k passos.
Definic
ao 2.16. [Classe de Complexidade NTIME]. Seja T : N N uma funcao. Uma
linguagem L {0, 1}? pertence a classe NTIME(T (n)) se existe uma maquina de Turing
nao-determinstica M que decide L em tempo O(T (n)).
A classe NP foi inicialmente definida atraves do uso de maquinas de Turing naodeterminsticas. Enquanto a sigla P expressa tempo polinomial, a sigla NP tem origem
em tempo polinomial nao-determinstico.
S
Teorema 2.17. NP = k1 NTIME(nk ).
Demonstracao. Duas ideias simples sao utilizadas na demonstracao desse resultado. Em
primeiro lugar, uma MTND e capaz de gerar em tempo polinomial qualquer certificado
possvel a partir das suas escolhas nao-determinsticas e entao verificar a presenca de uma
palavra na linguagem. Similarmente, a sequencia de escolhas das funcoes de transicao que
levam ao estado qaceitar pode ser usada como um certificado.
Suponha que L NP. Seja V um verificador para L, p(x) o polinomio que descreve
o tamanho dos certificados e assuma que V computa em tempo O(q(n)) para algum
polinomio q(x). Considere a seguinte MTND M . Com entrada x, M faz p(|x|) escolhas
arbitrarias de uso das funcoes de transicao 0 e 1 , imprimindo em um espaco auxiliar da
sua fita os valores 0 e 1, respectivamente. Atraves disso, M gera um possvel certificado
w de tamanho p(|x|) para a entrada x. Apos essa primeira etapa, M simula atraves
de uma computacao determinstica (ou seja, as duas funcoes de transicao coincidem)
o processamento de V com a entrada hx, wi. M entra no estado qaceitar se e somente
se V (x, w) = 1. Como V e um verificador para L, temos que x L se e somente se
M (x) = 1. A complexidade total de M e O(p(n) + q(n)), ou seja, existe k N tal que
L NTIME(nk ).
Suponha que L NTIME(nk ) para algum inteiro positivo k. Seja M uma MTND
que decide L em tempo O(nk ). Vamos mostrar que existe um verificador eficiente V
para L que trabalha com certificados de tamanho O(nk ). Com entrada hx, wi, V simula
a execucao de M com entrada x aplicando no i-esimo passo da simulacao a funcao de
transicao indicada pelo i-esimo bit do certificado w, e aceita a entrada hx, wi se e somente
se M (x) = 1 com essas escolhas. Segue imediatamente da definicao de aceitacao de uma
palavra por uma MTND que V e um verificador eficiente para L, ou seja, L NP.
claro que o uso de nao-determinismo permite que diversos problemas sejam resolE
vidos de forma muito mais simples. A grande pergunta e se esse recurso adicional pode
2.5. Reducoes e Problemas Completos
27
nos levar a um salto significativo de poder computacional. Em outras palavras, o problema P vs NP pergunta se maquinas eficientes determinsticas e nao-determinsticas sao
capazes de resolver os mesmos problemas. Pelo menos no caso mais trivial envolvendo
determinismo e nao-determinismo, sabemos provar que computacoes nao-determinsticas
sao mais poderosas.
Teorema 2.18. DTIME(n) ( NTIME(n).
Demonstracao. A prova desse resultado pode ser obtida em Paul et al. [89].
2.5
Reduc
oes e Problemas Completos
Ao final da decada de sessenta, uma grande classe de problemas computacionais para os

quais ninguem conhecia algoritmo eficiente foi identificada. A maioria deles sao problemas
de otimizacao como empacotamento otimo, agendamento de horarios e o problema do
caixeiro viajante. O que todos possuem em comum e uma grande quantidade de solucoes
possveis e nenhum metodo conhecido para buscar a solucao otima a nao ser essencialmente
a busca exaustiva. Apos grande quantidade de tempo e esforco despendidos na tentativa
de encontrar algoritmos eficientes para esses problemas, comecou-se a suspeitar que tais
algoritmos pudessem nao existir.
Apesar disso, nao havia motivos aparentes para a existencia de qualquer relacao entre
esses problemas, ou porque um deveria ser mais difcil do que o outro. A teoria de NPcompletude, introduzida por Cook [26] em 1971, trouxe exatamente a evidencia necessaria.
O que Cook mostrou em seu artigo foi que a existencia de um algoritmo eficiente para
qualquer um desses problemas garantia a existencia de algoritmos eficientes para todos os
outros problemas. Diversos problemas naturais possuem essa propriedade e sao chamados
de problemas NP-completos. Um ano mais tarde, Karp [66] utilizou os resultados de Cook
para incluir vinte novos problemas na lista de problemas NP-completos, demonstrando
a importancia do conceito descoberto. Mais tarde centenas de outros problemas NPcompletos foram identificados. Muitos desses sao de extrema importancia industrial, como
aqueles de roteamento e agendamento. Para entender esses resultados e preciso estudar o
conceito de reducao entre problemas computacionais.
A nocao de reducao entre problemas e amplamente utilizada em computacao. Em
geral, uma liguagem L1 pode ser reduzida a` linguagem L2 se a existencia de um algoritmo
A2 que decide L2 pode ser usada para a criacao de um algoritmo A1 capaz de decidir
L1 . Existem diversas maneiras de formalizar o conceito de reducao. A forma de reducao
mais abrangente e aquela em que permitimos que o algoritmo A1 invoque diversas vezes
o algoritmo A2 como subrotina.
28
Suponha que uma linguagem L1 seja redutvel a uma linguagem L2 . Se resolvemos

o problema de decisao L2 , entao tambem sabemos resolver o problema de decisao L1 .
Por isso, podemos considerar que L2 e pelo menos tao difcil quanto L1 . Em complexidade computacional estamos interessados principalmente em reducoes eficientes, ou seja,
computadas em tempo polinomial.
Suponha que P 6= NP. Para provarmos isso, precisamos exibir uma linguagem L em
NP que nao esta em P. Se for possvel determinar quais sao as linguagens mais difceis
em NP, entao essas serao boas candidatas para esse papel. De modo surpreendente, o que
Cook provou no seu artigo e que existem problemas em NP que sao tao difceis quanto
qualquer outro problema em NP. Em outras palavras, existe uma linguagem L em NP tal
que qualquer outra linguagem em NP se reduz à L. Alem do mais, uma nocao de reducao
mais restrita e suficiente para provar esse resultado.
Definic
ao 2.19. [Reducao de Karp]. Uma linguagem L {0, 1}? e Karp-redutvel a uma
linguagem L0 {0, 1}? (denotado por L p L0 ) se existe uma funcao f : {0, 1}? {0, 1}?
computavel em tempo polinomial tal que para todo x {0, 1}? , x L se e somente se
f (x) L0 .
Como a composicao de polinomios e novamente um polinomio, temos que a reducao
de Karp e uma relacao transitiva entre pares de linguagens. Alem disso, e facil verificar
que se L p L0 e L0 P, entao L P.
Definic
ao 2.20. [NP-difcil e NP-completo]. Dizemos que uma linguagem L0 {0, 1}? e
NP-difcil se L p L0 para toda linguagem L NP. Dizemos que L0 e NP-completa se L0
e NP-difcil e L0 NP.
O seguinte resultado confirma o papel fundamental exercido pelos problemas NPcompletos.
Teorema 2.21. Se L e NP-difcil e L P, entao P = NP.
Demonstracao. Seja L0 NP. Entao, por hipotese, L0 p L. Como L P, segue atraves da
composicao do algoritmo eficiente para L e do algoritmo eficiente que computa a reducao
que L0 P. Isso prova que NP P e portanto P = NP.
Em particular, se L e uma linguagem NP-completa, entao L P se e somente se P =
NP. O proximo teorema prova que existem linguagens com essa propriedade especial.
Teorema 2.22. Existem linguagens NP-completas.
Demonstracao. Primeiro mostramos que existe uma linguagem L0 que e NP-difcil. Precisamos provar que para todo L NP, temos L p L0 . Em outras palavras, temos que
2.5. Reducoes e Problemas Completos
29
mostrar que existe funcao fL : {0, 1}? {0, 1}? computavel eficientemente tal que x L
se e somente se fL (x) L0 . Dada uma linguagem arbitraria L NP, o que sabemos sobre
ela? Apenas que existe um verificador VL eficiente para L capaz de testar corretamente
certificados de tamanho pL (|x|). Como precisamos acomodar todas as reducoes possveis
utilizando apenas essas informacoes, considere a seguinte definicao para L0 :
L0 = {hV, x, 1k i : w {0, 1}k tal que V (x, w) = 1}.
Observe que x L se e somente se hVL , x, 1pL (|x|) i L0 . Alem disso, a funcao fL (x) =
hVL , x, 1pL (|x|) i pode ser computada eficientemente. Isso prova que L0 e NP-difcil.
O principal impedimento para mostrarmos que L0 e NP-completa, ou seja, pertence
a` classe NP, e o fato de que w nao e um certificado eficientemente verificavel para L0 .
Embora w seja sucinto, como a maquina V da instancia de entrada e arbitraria, nao
podemos garantir que a sada de V com entrada hx, wi pode ser computada em tempo
limitado por algum polinomio fixo. Para superar essa limitacao, adicionamos um novo
ingrediente à definicao de L0 :
L0 = {hV, x, 1k , 1t i : w {0, 1}k tal que V (x, w) = 1 em no maximo t passos }.
Seja qL (x) o polinomio que limita o tempo de execucao de VL . Entao x L se e somente
se hVL , x, 1pL (|x|) , 1qL (|x|) i L0 . Alem disso, a nova reducao tambem pode ser computada
em tempo polinomial. Portanto, L0 permanece NP-difcil. Por outro lado, temos agora
que w e um certificado sucinto e eficientemente checavel para a presenca de uma palavra
em L0 . Isso demonstra que L0 NP, ou seja, L0 e uma linguagem NP-completa.
Embora o problema utilizado na demonstracao anterior seja importante conceitualmente, ele nao e muito natural. Um segundo fato surpreendente e que existem problemas
NP-completos bastante naturais e de interesse pratico. Na verdade, atualmente sao conhecidos milhares de problemas com essa propriedade (veja a secao de referencias adicionais
deste captulo). O mais famoso deles e apresentado a seguir.
Definic
ao 2.23. [Linguagem SAT]. Uma formula proposicional em forma normal conjuntiva sobre as variaveis x1 , . . . , xn consiste em uma expresssao do tipo:

V W
(x1 , . . . , xn ) = i
u
j ij ,
onde cada uij e uma variavel xk ou a sua negacao xk . Uma formula desse tipo induz
naturalmente uma funcao booleana : {0, 1}n {0, 1} obtida atraves da aplicac
ao dos
conectivos , e aos bits de entrada. Dizemos que uma formula e satisfatvel se existe
~x {0, 1}n tal que (~x) = 1. Denotamos por SAT o conjunto de formulas proposicionais
satisfatveis em forma normal conjuntiva.
Teorema 2.24. [Teorema de Cook-Levin]. SAT e uma linguagem NP-completa.
30
Demonstracao. O fato de que SAT NP e facil de ser provado, pois os certificados

canonicos sao as proprias sequencias de bits que tornam verdadeira a formula de entrada.
A demonstracao de que SAT e NP-difcil tambem e conceitualmente simples. A principal
dificuldade e descrever precisamente os detalhes tecnicos da prova. Vamos apenas destacar
os pontos importantes da demonstracao.
Suponha que, para toda maquina de Turing M e para toda entrada x de tamanho n,
exista uma formula proposicional M,n tal que M (x) = 1 se e somente se M,n (x) = 1.
Alem disso, caso M seja uma maquina eficiente, assuma que a formula M,n pode ser
computada em tempo polinomial. Seja L NP e V um verificador para essa linguagem
que computa em tempo polinomial. Sabemos que x L se e somente se V (x, w) = 1 para
algum certificado w adequado. Note que as hipoteses anteriores garantem que podemos
criar uma formula V,x tal que V (x, w) = 1 se e somente se V,x (w) = 1. Isso pode ser
feito em tempo polinomial e portanto L p SAT.
Embora o argumento anterior possa ser usado para provar que um problema similar envolvendo circuitos booleanos e NP-difcil, existe uma dificuldade adicional quando
lidamos com formulas proposicionais. Ao contrario do que ocorre com os circuitos, as
formulas nao podem reaproveitar computacoes parciais. Por isso, nao esta claro se e
possvel criar uma formula de tamanho polinomial que simula a computacao de um algoritmo. No entanto, formulas proposicionais sao suficientemente expressivas para verificar
todas as condicoes locais de consistencia em uma tabela que descreve a computacao de
M com entrada x. Por isso, obtemos para toda maquina de Turing M e para toda entrada x de tamanho n uma formula proposicional M,n tal que M (x) = 1 se e somente
se M,n (Cx ) = 1, onde Cx e uma tabela que descreve consistentemente a computacao de
M com entrada x. Portanto, M (x) = 1 se e somente se a formula M,n e satisfatvel.
Como o verificador utilizado na reducao e uma maquina eficiente, a tabela que descreve
sua computacao tem tamanho polinomial, assim como a formula proposicional resultante.
Isso completa a demontracao de que SAT e NP-difcil.
A reducao anterior possui algumas propriedades adicionais muito interessantes. Primeiro, o n
umero de certificados aceitos pelo verificador original e igual ao n
umero de
atribuicoes que satisfazem a formula proposicional obtida. Alem disso, toda atribuicao
satisfatvel pode ser convertida eficientemente em um certificado aceito pelo verificador
original, e vice-versa.
Os detalhes tecnicos da prova residem no modo de construcao da formula proposicional
a partir da maquina de Turing. Uma descricao detalhada pode ser obtida no livro de Sipser
[103]. Uma tecnica um pouco mais eficiente pode ser usada para diminuir o tamanho da
formula proposicional obtida. Veja essa demonstracao no livro de Arora e Barak [7].
Devido a` transitividade da reducao de Karp e ao teorema anterior, para provar que um
problema arbitrario L e NP-completo, basta mostrar que L NP e SAT p L. Um outro
2.6. Importancia Matematica
31
exemplo de problema NP-completo e a versao generalizada do quebra-cabecas Sudoku

(veja Yato e Seta [115]). Devido ao teorema 2.21, se P 6= NP nenhum desses problemas
admite algoritmos eficientes.
Embora a teoria de NP-completude tenha obtido resultados surpreendentes e tenha
apontado novas direcoes frutferas de pesquisa, questoes muito simples ainda permanecem
em aberto.
Quest
ao em Aberto 2.25. SAT DTIME(n)?
Entretanto, somos capazes de provar que uma outra classe interessante de algoritmos
nao e capaz de resolver SAT (veja a secao 4.3).
2.6
Import
ancia Matem
atica
No incio do seculo passado, descobriu-se que o uso intuitivo e indiscriminado de diversas nocoes matematicas basicas poderia levar ao surgimento de inconsistencias logicas.
Esse fato inusitado provocou um enorme desenvolvimento no estudo da matematica, e
diversos sistemas formais foram sugeridos na tentativa de construir a matematica a partir
de bases mais seguras. Dentre os diversos sistemas axiomaticos formais propostos, um
dos mais importantes e a teoria de conjuntos conhecida como ZFC (Teoria de Conjuntos
Zermelo-Fraenkel with Choice).
Essa teoria possui tres propriedades muito interessantes. Em primeiro lugar, todos os
teoremas matematicos usuais podem ser provados a partir dos axiomas e regras do sistema
ZFC (veja Cohen e Davis [23]). Alem disso, a linguagem utilizada na demonstracao de
teoremas a partir dos axiomas dessa teoria e completamente formalizada. Por u
ltimo, no
sistema ZFC podemos verificar a validade de uma prova em tempo polinomial no tamanho
da demonstracao. Essas propriedades garantem que um algoritmo ou computador pode
ser utilizado para o estudo de diversas questoes relacionadas com esse sistema e com a
matematica em geral.
Em virtude disso, um matematico muito importante em sua epoca, chamado David
Hilbert, estava interessado na criacao de um algoritmo capaz de verificar automaticamente
se uma dada afirmacao matematica e um teorema. Essa questao ficou conhecida como
o Entscheidungsproblem, ou seja, o problema de decisao. Para o espanto de todos, Alan
Turing provou em 1936 [107] que nao existe algoritmo para resolver este problema.
Apesar desse resultado de impossibilidade, a complexidade computacional inspirou o
estudo de uma versao moderna desse problema. Considere a seguinte linguagem:
MATEMATICA
= {h, 1n i : existe uma prova de em ZFC de tamanho n}.
32
Essa linguagem, alem de ser decidvel (basta testar todas as provas possveis de tamanho
menor ou igual a n), tambem pertence a` classe de complexidade NP. Isso ocorre pois
uma demonstracao de tamanho k n para o teorema serve como certificado para sua
presenca na linguagem MATEMATICA

(lembre que podemos verificar eficientemente se
uma demonstracao e valida). Alem disso, e possvel provar que esse problema e NPcompleto. Isso segue do fato de que uma formula proposicional e satisfatvel se e somente
se existe uma demonstracao sucinta de sua satisfatibilidade no sistema ZFC.
Suponha que exista um algoritmo eficiente para o problema MATEMATICA.

Entao,
para descobrirmos se somos capazes de demonstrar um teorema basta executar esse
algoritmo com a entrada h, 1n i para um inteiro n suficientemente grande (existe uma
relacao polinomial entre o tamanho de uma demonstracao matematica usual e o tamanho
de uma demonstracao formal dentro do sistema ZFC). Se a resposta do algoritmo for
negativa, entao nao precisamos nem perder nosso tempo a` procura de uma demonstracao
para (se existe alguma demonstracao para esse resultado, ela e tao grande que seria
humanamente impossvel encontra-la). Alem disso, como essa linguagem e NP-completa, a
existencia de um algoritmo eficiente para esse problema implica que P = NP. Pelo teorema
2.15, segue que tambem seremos capazes de encontrar a demonstracao procurada, caso
ela exista.
Por isso, podemos dizer que P = NP se e somente se o trabalho de um matematico
pode ser eficientemente mecanizado. Em outras palavras, a menos que essas duas classes
coincidam, a criatividade e essencial no processo de construcao de uma prova matematica.
2.7
Principais Abordagens
Suponha que P = NP e considere como isso poderia ser demonstrado. A maneira

mais natural seria exibir um algoritmo polinomial para a linguagem SAT ou para algum
outro problema NP-completo. Existe uma serie de metodos algortmicos que podem ser
utilizados para isso. As principais tecnicas podem ser encontradas em Cormen et al. [29].
Devido a` grande importancia industrial de diversos problemas NP-completos, um imenso
n
umero de programadores e engenheiros tentaram encontrar algoritmos eficientes para
esses problemas durante as u
ltimas decadas, mas nao obtiveram sucesso.
Um metodo algortmico interessante e a modelagem de problemas computacionais
atraves de programacao linear. Como esse u
ltimo problema pode ser resolvido em tempo
polinomial, se for possvel reduzir eficientemente algum problema NP-completo à um
problema de programacao linear, ficara provado que P = NP. No entanto, Yannakakis
[114] mostrou que um importante problema NP-completo conhecido como TSP (problema
do caixeiro viajante) nao possui formulacao eficiente como um problema de programacao
linear com certas restricoes. Isso ilustra o fato de que e possvel demonstrar que certas
2.7. Principais Abordagens
33
abordagens nao sao suficientes para provar que P = NP.

Por outro lado, caso P 6= NP, existem muitos metodos que foram propostos na tentativa de provar esse resultado. Alguns deles foram amplamente estudados e algumas
limitacoes importantes tambem foram descobertas. Discutimos a seguir os casos mais
interessantes.
Simulac
ao e Diagonalizac
ao
O metodo de diagonalizacao teve origem com a demonstracao de Cantor de que o
conjunto de n
umeros reais nao e enumeravel. Adaptado à teoria da computacao, esse
metodo foi utilizado inicialmente para provar que certos problemas computacionais sao
indecidveis. Em complexidade, um argumento envolvendo simulacao e diagonalizacao
pode ser aplicado para demonstrar que existem problemas computacionais arbitrariamente
difceis. Veremos como isso pode ser feito no captulo 3.
Alem disso, a diagonalizacao pode ser usada para provar limitantes inferiores superexponencias na complexidade de alguns problemas importantes (veja por exemplo o artigo
de Fischer e Rabin [36]). Apesar dessa tecnica ser extremamente poderosa, ha evidencias
fortes de que ela sozinha nao e suficiente para separar as classes de complexidade P e NP.
Ainda que a tecnica de diagonalizacao possua essa importante limitacao, quando combinada com outros metodos, ela e capaz de provar resultados interessantes em complexidade
computacional. Vamos discutir essa questao em profundidade no captulo 5.
Complexidade de Circuitos
Como veremos posteriormente, a relativizacao das tecnicas baseadas apenas em simulacao e diagonalizacao indica que devemos de fato analisar as computacoes envolvidas,
e nao apenas simula-las. Alguns resultados importantes provados na decada de oitenta
tornaram interessante o estudo de certos problemas atraves do uso de circuitos booleanos.
Na complexidade de circuitos, as funcoes sao classificadas de acordo com o tamanho (quantidade de portas logicas) e a profundidade dos circuitos booleanos capazes de
computa-las. Um aspecto interessante desse modelo computacional de computacao e a
falta de uniformidade. Isso significa que, ao contrario das maquinas de Turing, entradas
com tamanhos diferentes sao processadas por circuitos booleanos diferentes.
O problema P vs NP e abordado atraves da complexidade de circuitos da seguinte
maneira. Em primeiro lugar, para toda linguagem em P existe uma famlia de circuitos
booleanos com uma quantidade polinomial de portas logicas (em funcao do tamanho da
entrada) capaz de decid-la. Por outro lado, ha fortes evidencias de que os problemas
NP-completos nao podem ser computados por famlias de circuitos de tamanho polino-
34
mial. Como circuitos booleanos sao muito mais simples que maquinas de Turing, diversos
metodos combinatorios e probabilsticos podem ser utilizados na tentativa de provar que
alguma linguagem NP-completa nao admite circuitos eficientes.
Embora essa abordagem tenha tido algum sucesso com modelos mais restritos de circuitos booleanos, os melhores resultados obtidos para o caso geral sao muito fracos. Assim
como ocorre com a diagonalizacao, tambem e possvel justificar parte do fracasso dessa
abordagem. Discutiremos novamente essa questao na secao 5.8.
M
etodos Alg
ebricos
Apos a descoberta das barreiras descritas anteriormente, um novo metodo mostrou-se
interessante para o estudo da relacao entre classes de complexidade. Uma tecnica baseada
na aritmetizacao de formulas logicas foi capaz de provar resultados importantes, como a
caracterizacao de classes3 IP = PSPACE [101]. Alem disso, foram descobertas demonstracoes que ultrapassam simultaneamente as barreiras envolvendo os metodos anteriores.
Caracterizac
ao L
ogica das Classes de Complexidade
A questao P vs NP e equivalente a um problema de expressividade envolvendo duas
classes distintas de expressoes logicas. Todas as linguagens em P podem ser representadas por meio de formulas logicas de primeira ordem envolvendo um operador adicional de
ponto fixo. Similarmente, as linguagens em NP sao capturadas pelas expressoes logicas
em linguagem de segunda-ordem existencial. Portanto, o problema P vs NP e equivalente
a` seguinte questao: a logica de segunda-ordem existencial e capaz de descrever mais linguagens do que a logica de primeira ordem com o operador de ponto fixo? Um ponto
forte dessa abordagem e a disponibilidade de metodos bastante estudados proveninentes
da logica matematica.
GCT - Geometric Complexity Theory
Esse e um metodo recente proposto por Mulmuney e Sohoni em uma serie de artigos
publicados nos u
ltimos anos. Esses autores argumentam que diversas dificuldades enfrentadas pelos metodos anteriores podem ser formalmente analisadas e superadas atraves da
geometria algebrica e da teoria de representacoes.
Em alguns casos, a prova de um limitante superior implica na demonstracao de um
3
Para uma definic

ao da classe probabilstica IP, recomendamos a leitura do livro de Goldreich [47].
A classe PSPACE contem as linguagens que podem ser decididas em espaco polinomial. Veja o captulo
3 para mais detalhes.
2.8. Resultados Basicos
35
limitante inferior. Por exemplo, um resultado famoso de Kannan [64] mostra que, para
todo inteiro k, existem linguagens na hierarquia polinomial (definida na secao 4.1) com
complexidade de circuito (nk ). Por outro lado, e facil provar que se P = NP entao a
hierarquia polinomial coincide com a classe P (veja a secao 4.1). Por isso, basta demonstrar
0
que existe um inteiro k 0 tal que toda linguagem em P possui circuitos de tamanho O(nk )
para mostrar que P 6= NP. Esse exemplo mostra que se os problemas em P sao faceis
demais, entao ha problemas em NP que sao difceis.
A principal ideia por tras da abordagem GCT e baseada em um argumento similar,
porem aplicado em um contexto diferente. Essencialmente, para provar que P 6= NP
basta demonstrar que diversos problemas de decisao em geometria algebrica e teoria de
representacoes percentem a` classe P. A abordagem utiliza tecnicas matematicas bastante
avancadas e os autores admitem que o desenvolvimento completo desse projeto pode levar
decadas. Veja a secao de referencias deste captulo para mais detalhes.
2.8
Resultados B
asicos
Nesta secao introduzimos duas novas classes de complexidade e relacionamos atraves

de alguns resultados simples todas as classes discutidas ate agora.
Lembre que o problema P vs NP pode ser enunciado como o estudo da relacao entre
maquinas eficientes determinsticas e nao-determinticas. Para entendermos melhor a
diferenca entre determinismo e nao-determinismo e interessante o estudo desses conceitos
em maquinas com muito mais poder computacional. Para isso, introduzimos a seguir as
classes EXP e NEXP.
Definic
ao 2.26. [Classe de Complexidade EXP].
S
k
EXP = k1 DTIME(2n ).
Definic
ao 2.27. [Classe de Complexidade NEXP].
S
k
NEXP = k1 NTIME(2n ).
Primeiro, enunciamos um fato muito simples envolvendo as novas classes.
Lema 2.28. P NP EXP NEXP.
Demonstracao. A primeira inclusao foi provado no lema 2.13 e a u
ltima inclusao e imediata. Suponha que L NP e seja V um verificador para L de complexidade O(nc ). Alem
disso, considere que os certificados aceitos por V possuam tamanho O(nd ). Dada uma
entrada x {0, 1}? , podemos decidir se x L deterministicamente enumerando todos os
d
O(2n ) certificados possveis e utilizando a maquina V para checar se alguns deles e um cerd
tificado valido para x. Isso pode ser feito em tempo determinstico O(2n nd ) e, portanto,
d+1
em tempo determinstico O(2n ). Logo, temos L EXP e portanto NP EXP.
36
De forma analoga ao problema P vs NP, temos a seguinte conjectura.

Quest
ao em Aberto 2.29. EXP = NEXP ?
As conjecturas envolvendo o poder do nao-determinismo em computacao podem ser
relacionadas atraves do seguinte teorema.
Teorema 2.30. Se P = NP entao EXP = NEXP.
Demonstracao. Utilizaremos um argumento muito u
til em complexidade computacional
que e conhecido como metodo do preenchimento. Basicamente, adicionamos diversos bits
redundantes às palavras que representam as instancias de uma linguagem para reduzirmos
sua complexidade total.
Suponha que L NEXP, ou seja, existe uma MTND M que decide L em no maximo
0 nk
k 2 passos. Temos entao que a linguagem
0 |x|k
Lpreenchida = {hx, 1k 2
i : x L}
esta em NP, uma vez que a seguinte MTND M 0 decide Lpreenchida eficientemente: dado
0 |z|k
y {0, 1}? , primeiro M 0 verifica se y = hz, 1k 2 i para alguma palavra z. Se isso nao
k
ocorre, M 0 rejeita y. Caso contrario, M 0 simula a maquina M com entrada z por ate k 0 2|z|
passos e aceita ou rejeita a entrada y de acordo com a decisao de M . Devido ao nosso
preenchimento, temos que M 0 computa em tempo polinomial no tamanho de y, ou seja,
Lpreenchida NP. Porem, por hipotese, temos que P = NP e portanto Lpreenchida P. Utilizando uma maquina determinstica de tempo polinomial que decide Lpreenchida podemos
decidir L em tempo determinstico exponencial: basta adicionar os bits de preenchimento
e aplicar a maquina eficiente de Lpreenchida . Isso prova que NEXP EXP e portanto EXP
= NEXP.
Observe que para provar que P 6= NP basta demonstrar que EXP 6= NEXP.
O resultado anterior mostra que, para alguns recursos computacionais, a igualdade
entre classes de complexidade inferiores pode ser estendida às classes de complexidade
possvel demonstrar uma versao mais geral do teorema 2.30, valida tanto
superiores. E
para tempo quanto para espaco. Veja o livro de Papadimitriou [88] para mais detalhes.
Veremos no captulo 3 que muitos resultados desse tipo podem ser unificados atraves de
uma nocao mais abrangente de complexidade de tempo e espaco.
Embora alguns problemas discutidos anteriormente permanecam em aberto, provaremos no proximo captulo que P 6= EXP e NP 6= NEXP.
2.9
37
Refer
encias Adicionais
Os primeiros textos que consideram a questao da eficiencia dos algoritmos sao os

artigos de Cobham [22] e Edmonds [34]. Em particular, o artigo de Edmonds demonstra
a existencia de um algoritmo eficiente para o problema do emparelhamento em grafos
arbitrarios. Diversos algoritmos para o problema do caminho mnimo sao descritos no
livro de Cormen et al. [29].
O enunciado do problema P vs NP pode ser obtido no artigo de Cook [28]. Historicamente, um enunciado equivalente desse problema apareceu pela primeira vez em uma
carta de Kurt Godel enviada para Von Neumann em 1956. Basicamente, Godel indagou
se existe algum algoritmo eficiente para o problema computacional NP-completo discutido
na secao 2.6, notando que esse fato teria consequencias fantasticas para a matematica. O
conte
udo completo da carta esta disponvel no artigo de Sipser [102].
O algoritmo de primalidade AKS foi desenvolvido por Agrawal, Kayal e Saxena [6]. Ele
foi o primeiro algoritmo de primalidade proposto que e ao mesmo tempo geral, determinstico, eficiente e incondicional. Uma descricao informal das principais ideias utilizadas
no algoritmo AKS pode ser encontrada no artigo de Aaronson [3]. Uma referencia em
portugues sobre esse teste de primalidade e o livro de Coutinho [30]. Antes do desenvolvimento do algoritmo AKS, Miller [81] apresentou um algoritmo eficiente para o mesmo
problema assumindo a hipotese de Riemann generalizada.
A questao NP vs coNP esta intimamente relacionada com uma area de pesquisa chamada complexidade de prova. O principal objetivo dessa disciplina e demonstrar que nao
existem provas sucintas e facilmente verificaveis de que uma formula proposicional e uma
tautologia. Isso separaria as classes NP e coNP, provando que P 6= NP. Uma referencia
recente sobre o tema e o livro de Cook e Nguyen [25].
A secao 2.4 e baseada no livro de Arora e Barak [7] e a secao 2.6 e motivada por uma
discussao apresentada no livro de Immerman [61].
A descoberta da existencia de problemas NP-completos foi feita independentemente
por Cook [26] e Levin [74]. O livro de Garey e Johnson [45] e a referencia classica sobre
problemas NP-completos.
O artigo de Sipser e Boppana [15], embora nao seja muito recente, ainda descreve os
pricipais resultados obtidos em complexidade de circuitos. O livro de Immerman [61] e
inteiramente dedicado a` relacao entre logica e complexidade computacional. A abordagem
GCT para o problema P vs NP esta resumida no artigo de Regan [91]. Na pagina pessoal
de Ketan Mulmuney ha uma serie de artigos sobre o tema.
Ao longo de decadas diversas pessoas afirmaram ter uma solucao para o problema P
vs NP. Veja o site [112] para mais detalhes.
O artigo de Aaronson [4] ilustra algumas consequencias interessantes para a fsica se
38
assumirmos que os problemas NP-completos nao podem ser resolvidos de forma eficiente
no universo fsico. Veja tambem o site [1] mantido pelo mesmo autor para uma descricao
de centenas de classes de complexidade estudadas em complexidade computacional.
Captulo 3
Simula
c
ao e Diagonaliza
c
ao
Time is the most valuable thing a man can spend.
Theophrastus.
Intuitivamente, esperamos que com mais recursos computacionais seja possvel resolver mais problemas. Os teoremas de hierarquia de tempo e de espaco,
alguns dos resultados mais importantes provados em complexidade computacional, estabelecem exatamente isso. O argumento utilizado na prova desses
teoremas e conhecido como metodo da diagonalizacao. Neste captulo vamos
estudar essa tecnica em profundidade. Veremos tambem como generalizar e
unificar a demonstracao dos teoremas de hierarquia e de outros resultados importantes em complexidade computacional.
3.1
Introduc
ao
Em um artigo muito importante para a teoria de complexidade computacional, Hartmanis e Stearn [54] provaram que e possvel resolver mais problemas computacionais
quando se tem mais tempo disponvel. Em outras palavras, eles demonstraram a existencia de problemas computacionais decidveis porem arbitrariamente difceis. Por exemplo,
existem linguagens que ate podem ser decididas em tempo polinomial, mas nunca em
tempo O(n3 ). Similarmente, pode-se provar que o mesmo fenomeno ocorre quando consideramos a complexidade de espaco ao inves da complexidade de tempo [104]. Esses
resultados ficaram conhecidos como teoremas de hierarquia.
O principal argumento utilizado na demonstracao desses resultados e uma combinacao
de simulacao e diagonalizacao. Embora essas ideias nao sejam novas, esse e o u
nico
39
40
Captulo 3. Simulacao e Diagonalizacao
metodo conhecido capaz de separar certas classes de complexidade importantes. Por isso,
entender os pontos fortes e os limites da diagonalizacao e fundamental para o estudo de
complexidade computacional.
Antes de provarmos uma forma bastante geral do teorema da hierarquia, vamos melhorar nossa intuicao atraves de um exemplo mais simples. Se necessario, revise a definicao
de complexidade de espaco apresentada na secao 1.7.
Definic
ao 3.1. [Classe de Complexidade DSPACE]. Seja S : N N uma funcao. Uma
linguagem L {0, 1}? pertence a classe DSPACE(S(n)) se existe uma maquina de Turing
M que decide L e que tenha complexidade de espaco O(S(n)).
Teorema 3.2. DSPACE(n) ( DSPACE(n3 ).
imediato que DSPACE(n) DSPACE(n3 ). Considere agora a seguinte
Demonstracao. E
linguagem:
L = {hM i : M e uma maquina de Turing que aceita hM i e sM (hM i) |hM i|1.5 }.
Por conveniencia, na definicao da linguagem L utilizamos a propria descricao da maquina
de Turing como entrada para sua computacao. Observe que, permitindo entradas arbitrarias para cada maquina de Turing, podemos obter uma linguagem L0 capaz de codificar
as instancias de todos os problemas que podem ser resolvidos em tempo n1.2 , por exemplo
(no sentido da demontracao do teorema 2.22). Isso explica, de certa forma, porque L e
uma linguagem tao difcil para computacoes que utilizam espaco linear. Vamos dividir a
demonstracao desse teorema em dois lemas.
Lema 3.3. L DSPACE(n3 ).
Demonstracao. A prova deste lema ilustra o conceito de simulacao entre maquinas de
Turing. Precisamos mostrar que existe uma maquina de Turing U satisfazendo as seguintes
propriedades: (1) U aceita a palavra hM i se e somente se M aceita seu proprio codigo
utilizando no maximo |hM i|1.5 celulas de memoria; (2) U utiliza espaco O(n3 ), onde
n = |hM i| e o tamanho da palavra de entrada; (3) U sempre termina sua computacao.
Para simular a computacao de M , a maquina U utiliza tres fitas de memoria. A
primeira fita de U armazena a entrada hM i. Na segunda fita, U guarda o estado atual
de M durante a simulacao e o n
umero de celulas de memoria acessadas por M ate o
momento. Por u
ltimo, a terceira fita de U armazena de forma concatenada o conte
udo
das fitas de memoria de M durante a sua computacao. Smbolos especiais sao utilizados
na terceira fita para indicar a posicao de cada cabeca de leitura de M durante a simulacao.
No incio da simulacao, U copia a palavra de entrada para o incio da terceira fita, de
modo que a palavra hM i sirva como entrada para a maquina M .
3.1. Introducao
41
Para simular um passo de M , a maquina U verifica o smbolo lido por cada cabeca
de leitura de M (fita 3), o estado atual de M (fita 2) e sua tabela de transicao (fita 1).
Informacoes auxiliares utilizadas por U para processar essas informacoes sao mantidas na
segunda fita. A maquina U atualiza sua terceira fita de modo a refletir o conte
udo das
fitas da maquina M apos cada passo da simulacao. Se necessario, algumas fitas de M
sao deslocadas para a direita na terceira fita de U para garantir espaco para outras fitas.
U atualiza as informacoes na fita 2 e prossegue para o proximo passo da simulacao. Se
em algum momento M aceita ou rejeita seu proprio codigo, U toma a mesma decisao.
Caso M acesse mais do que n1.5 celulas de memoria, a maquina U rejeita a entrada hM i.
Claramente, com essa descricao temos que U satisfaz o primeiro requisito desejado.
A primeira fita de U utiliza durante a computacao n celulas de memoria. A terceira
fita nao utiliza mais do que n1.5 celulas, pois caso esse limite seja ultrapassado, a simulacao
e interrompida e U rejeita a entrada hM i. Por u
ltimo, o contador de celulas de memoria
utilizadas por M e os dados auxiliares armazenados na segunda fita nao utilizam mais
do que c1 n celulas de memoria para alguma constante c1 que depende dos detalhes de
implementacao da maquina U . Isso prova que U utiliza no maximo O(n1.5 ) celulas de
memoria.
No entanto, observe que a maquina simulada pode executar indefinidamente enquanto
utiliza uma quantidade finita de memoria. Por isso, a descricao atual da maquina U
nao satisfaz o requisito (3). Veremos que nao e difcil descobrir quando essa situacao
ocorre. Lembre que a descricao de M tem tamanho n. Durante a simulacao: (1) M
pode utilizar no maximo n1.5 celulas de memoria; (2) M possui no maximo n fitas de
leitura; (3) o n
umero maximo de estados de M e de smbolos no seu alfabeto e n. Observe
que essas informacoes determinam completamente o estado atual da computacao de M
(tambem chamado de configuracao de M ). Alem do mais, combinando o conte
udo das
fitas de M , o seu estado atual e a posicao de cada cabeca de leitura, temos que existem
1.5
no maximo (nnn )(n)(n1.5 )n configuracoes distintas possveis. Isso significa que, apos
2.5
nn +1.5n+1 passos simulados, podemos rejeitar a maquina de entrada, pois nesse caso
sabemos que M repete alguma configuracao e portanto computa indefinidamente, ou
seja, hM i
/ L. Alteramos a maquina U para que ela conte o n
umero de passos realizados
por M (na segunda fita) e verifique quando isso ocorre. O espaco adicional utilizado por
2.5
U e de no maximo k log nn +1.5n+1 celulas, para alguma constante k adequada. Ou seja,
o espaco total utilizado por M ainda e O(n3 ). Isso completa a demonstracao de que
L DSPACE(n3 ).
Lema 3.4. L
/ DSPACE(n).
Demonstracao. A prova deste lema ilustra o argumento de diagonalizacao. Suponha que
L DSPACE(n), ou seja, existe uma maquina de Turing A que decide L e SA (n) e O(n).
42
facil perceber que DSPACE(n) e uma classe fechada por complementacao de linguagens
E
(basta inverter os estados de aceitacao e rejeicao da maquina de Turing). Portanto, seja
B uma maquina de Turing que decide a linguagem L em espaco linear. Suponha que hBi
seja uma palavra suficientemente grande que represente a maquina B (sempre podemos
adicionar tuplas irrelevantes à descricao hBi). Considere agora a computacao de A com
entrada hBi. Temos que A aceita hBi se e somente se B aceita hBi e sB (hBi) |hBi|1.5 ,
uma vez que A decide L. Por outro lado, isso ocorre se e somente se B aceita hBi,
pois a condicao sB (hBi) |hBi|1.5 e verdadeira ja que B computa em espaco linear e
hBi e uma palavra suficientemente grande. Finalmente, a u
ltima condicao ocorre se e
somente se A rejeita hBi, pois A decide L e B decide L. Essa contradicao mostra que
L
/ DSPACE(n).
Isso completa a demonstracao do teorema.
O teorema 3.2 pode ser utilizado para demonstrar que maquinas determinsticas que
utilizam espaco linear e maquinas nao-determinsticas eficientes nao sao capazes de resolver os mesmos problemas computacionais.
Definic
ao 3.5. Uma classe de complexidade R e fechada por reducao de tempo polinomial
se L R e L0 p L implicam L0 R.
Teorema 3.6. NP 6= DSPACE(n).
Demonstracao. Como a composicao de uma reducao computada em tempo polinomial
com uma MTND eficiente e novamente uma MTND eficiente, temos que NP e uma classe
fechada por reducao de tempo polinomial. Por outro lado, vamos utilizar o teorema 3.2
e o metodo do preenchimento para provar que DSPACE(n) nao possui essa propriedade.
Isso prova que NP 6= DSPACE(n).
De acordo com o teorema 3.2, existe uma linguagem L DSPACE(n3 ) \ DSPACE(n).
Suponha que L seja decidida por uma maquina de Turing ML que nunca utiliza mais que
kn3 celulas de suas fitas. Atraves de uma simples modificacao na maquina ML (despre3
zamos a sequencia final de 1s), temos que a linguagem Lpreenchida = {hw, 1k|w| i : w L}
esta em DSPACE(n). Alem disso, e imediato que L p Lpreenchida . Porem, por hipotese,
L
/ DSPACE(n). Isso mostra que DSPACE(n) nao e uma classe de complexidade fechada
por reducao de tempo polinomial.
Embora este possa parecer um resultado muito simples, ainda nao sabemos provar qual
inclusao entre essas classes e falsa (provavelmente, as duas inclusoes nao sao validas). O
mesmo argumento pode ser utilizado para demonstrar que P 6= DSPACE(n).
Outras duas classes de complexidade importantes sao definidas a seguir.
3.1. Introducao
43
Definic
ao 3.7. [Classe de Complexidade PSPACE].
S
PSPACE = k1 DSPACE(nk ).
Definic
ao 3.8. [Classe de Complexidade EXPSPACE].
S
k
EXPSPACE = k1 DSPACE(2n ).
Lema 3.9. PSPACE EXP.
Demonstracao. Para demonstrar isso, mostraremos que todo algoritmo determinstico
b+1
com complexidade de espaco O(nb ) possui complexidade de tempo O(2n ), onde b e
um inteiro positivo qualquer. Seja L PSPACE e considere que M e uma maquina de
umero de estados da
Turing que decide a linguagem L em espaco k1 nk2 . Sejam k3 o n
maquina M , k4 o n
umero de fitas de M e k5 o n
umeros de smbolos no seu alfabeto.
Antes de qualquer passo de sua computacao: (1) M pode estar em algum dos k3 estados;
(2) o n
umero maximo de combinacoes possveis para a localizacao das cabecas de leitura
k
de M e (k1 nk2 )k4 ; (3) existem no maximo (k5 )k4 k1 n 2 possibilidades para o conte
udo escrito nas fitas de M . Por isso, o n
umero maximo de configuracoes possveis para M e
k2 k4 k4 k1 nk2
nk2 +1
k3 (k1 n ) k5
c1 2
, onde c1 e uma constante que nao depende de n. Se M
k +1
computa com alguma entrada de tamanho n por mais do que c1 2n 2 passos, entao M
repete alguma configuracao anterior, entrando portanto em um laco infinito. Como M
sempre termina sua computacao (M decide L), isso nao e possvel. Portanto, M computa
k +1
em tempo O(2n 2 ), ou seja, L EXP.
Por outro lado, observe que NP PSPACE. Isso ocorre pois, dada uma entrada,
podemos reaproveitar o espaco utilizado por uma maquina de Turing determinstica de
tempo polinomial para checar todos as escolhas nao-determinsticas possveis de uma
MTND de tempo polinomial. Essa e uma vantagem fundamental da complexidade de
espaco em relacao a` complexidade de tempo. Segue atraves do mesmo argumento que
NEXP EXPSPACE. De fato, e possvel provar atraves de simulacao que espaco e um
recurso mais poderoso que tempo.
Teorema 3.10. Seja T (n) : N N uma funcao arbitraria.
Entao DTIME(T (n)) DSPACE(T (n)/ log T (n)).
Demonstracao. A prova desse teorema utiliza uma simulacao envolvendo blocos de memoria e pode ser obtida em Hopcroft et al. [58].
Vamos resumir no proximo enunciado o que sabemos sobre as classes de complexidade
estudadas ate agora.
Teorema 3.11. P NP PSPACE EXP NEXP EXPSPACE.
Demonstracao. Vimos na discussao anterior que NP PSPACE e NEXP EXPSPACE.
O resultado segue a partir dos lemas 2.28 e 3.9.
44
3.2
Um Teorema Geral de Hierarquia
Nosso proximo passo e provar um teorema geral de hierarquia e obter como corolarios
os teoremas de hierarquia classicos demonstrados por Hartmanis e Stearn [54, 104]. Por
simplicidade, vamos considerar nesta secao apenas maquinas de Turing determinsticas
com uma u
nica fita (veja a secao 1.8). Alem disso, assuma que todas as maquinas utilizam
o alfabeto {0, 1}. Veremos na proxima secao como converter esse resultado para maquinas
de Turing sem tais restricoes.
Primeiro, vamos definir uma nocao de complexidade um pouco mais geral do que a
usada ate agora.
Definic
ao 3.12. [f -complexidade]. Sejam M uma maquina de Turing e f : N N N
uma funcao arbitraria. Considere a funcao f-tsM : {0, 1}? N dada por f-tsM (x) =
f (tM (x), sM (x)). Dizemos que a f -complexidade de M e dada pela funcao f -TSM : N
N, onde f -TS(n) = max{ f-tsM (x) : x {0, 1}n }.
A funcao f introduz uma nova medida de complexidade baseada nas complexidades
de tempo e espaco da maquina de Turing. Claramente, se f e uma das projecoes binarias,
entao a f -complexidade obtida e a complexidade usual de tempo ou espaco.
Definic
ao 3.13. Uma linguagem L e decidvel em f -complexidade O(g(n)) se existe uma
maquina de Turing M decidindo L tal que f -TSM e O(g(n)).
O proximo resultado mostra que, para qualquer f -complexidade adotada, existem
problemas arbitrariamente difceis.
Definic
ao 3.14. Sejam f : N N N e g : N N funcoes arbitrarias. Definimos a
seguinte linguagem:
Lf,g = { hM i | M e uma maquina de Turing que aceita hM i e f-tsM (hM i) g(|hM i|) }.
(3.1)
Teorema 3.15. Nao existe maquina de Turing que decide Lf,g em f -complexidade o(g(n)).
Demonstracao. A fim de obtermos uma contradicao, suponha que uma maquina de Turing
A decida Lf,g e que f -TSA (n) seja o(g(n)). Considere a maquina de Turing B obtida a
partir de A atraves da troca de papeis entre os estados de aceitacao e rejeicao. Entao B
aceita w se e somente se A rejeita w, para todo w {0, 1}? .
Adicione diversas regras irrelevantes a` funcao de transicao de B, obtendo uma maquina
de Turing B 0 . Claramente,
L(B 0 ) = L(B) = {0, 1}? \ L(A).
(3.2)
3.2. Um Teorema Geral de Hierarquia
45
Alem disso, existe algum n0 N tal que f -TSA (n) g(n) para todo n n0 , uma
vez que f -TSA (n) e o(g(n)). Por isso, temos f -tsA (x) g(n) para todo x {0, 1}? com
n = |x| n0 . Porem, e imediato que f -tsA = f -tsB 0 , e portanto
f -tsB 0 (hB 0 i) g(|hB 0 i|)
(3.3)
se aumentarmos suficientemente a descricao de B ate obtermos |hB 0 i| n0 .

Considere agora a computacao de A com a entrada hB 0 i:
A aceita hB 0 i sse
(usando 3.1)
B 0 aceita hB 0 i e f -tsB 0 (hB 0 i) g(|hB 0 i|) sse

B 0 aceita hB 0 i sse
(usando 3.3)
(usando 3.2)
A rejeita hB 0 i.
Obtemos uma contradicao. Isso prova que nao existe maquina de Turing A capaz de
decidir Lf,g em f -complexidade o(g(n)).
Como a funcao f pode ser qualquer combinacao de tempo e espaco (f pode ser,
inclusive, uma funcao nao-computavel), o teorema 3.15 prova essencialmente que a melhor
maquina de Turing universal possvel e aquela que realiza uma simulacao passo a passo
da maquina de entrada.
Para ilustrar, seja g(n) = n3 e considere a projecao f (x, y) = x. Neste caso, a f complexidade corresponde à complexidade usual de tempo. Por isso, a linguagem Lf,g
pode ser descrita como o conjunto de palavras que representam maquinas de Turing que
aceitam seu proprio codigo em no maximo n3 passos. O teorema 3.15 prova que nao existe
maquina de Turing que decide Lf,g em tempo o(n3 ).
O proximo resultado mostra que podemos desprezar a complexidade das maquinas de
Turing envolvidas se tomarmos f como sendo a funcao identicamente nula.
Corol
ario 3.16. [Existencia de Problemas Indecidveis]. Sejam f : N N N a func
ao
identicamente nula e g : N N uma funcao arbitraria. Para f e g tomadas dessa forma,
a linguagem Lf,g da definicao 3.14 e indecidvel, i.e., nao existe maquina de Turing que
decide Lf,g .
Demonstracao. Seja M uma maquina de Turing que decide Lf,g . Como f e identicamente
nula e g possui imagem nao-negativa, temos que f -TSM e o(g(n)). Por isso, M decide
Lf,g em f -complexidade o(g(n)). No entanto, segue pelo teorema 3.15 que a linguagem
Lf,g nao pode ser decidida em f -complexidade o(g(n)). Essa contradicao completa a
demonstracao de que Lf,g e uma linguagem indecidvel.
46
No entanto, se a funcao f e uma medida de complexidade natural (veja abaixo), entao

e possvel provar que a f -complexidade obtida da origem a uma hierarquia de linguagens.
Podemos obter essa hierarquia calculando a f -complexidade de uma maquina de Turing
que decide Lf,g . Essa linguagem pode ser decidida simulando a maquina M com a entrada
hM i.
Definic
ao 3.17. Seja f : N N N uma funcao. Dizemos que f e uma medida de
complexidade natural se f satisfaz as seguintes propriedades: (1) f e uma funcao naodecrescente em cada uma de suas coordenadas; (2) f e uma funcao computavel; (3) para
todo par de inteiros t e s, temos que f (t, s) min{t, s}.
Vamos agora enunciar o teorema de hierarquia. Lembre que TM e SM denotam a
complexidade de tempo e espaco da maquina de Turing M .
Teorema 3.18. [Hierarquia de Espaco-Tempo]. Sejam f uma medida de complexidade
natural e g : N N uma funcao computavel tal que g(n) n. Assuma que as maquinas
de Turing Mf e Mg computam as funcoes f e g, respectivamente. Considere a linguagem
Lf,g como na definicao 3.14. Entao Lf,g pode ser decidida por uma maquina de Turing A
com f -complexidade O( f (TA (n), SA (n)) ), onde

TA (n) c4 TMg (n) + g(n) TMf (c3 g(n)) + SMg (n) + g(n) + SMf (c2 g(n))
(3.4)

(3.5)
SA (n) c1 SMg (n) + g(n) + SMf (c2 g(n))
e ci N e uma constante, 1 i 4. Alem disso, Lf,g nao pode ser decidida por uma
maquina de Turing com f -complexidade o(g(n)).
Demonstracao. Em primeiro lugar, segue pelo teorema 3.15 que a linguagem Lf,g nao
pode ser decidida por maquinas de Turing em f -complexidade o(g(n)). Por outro lado,
a maquina de Turing A apresentada a seguir decide Lf,g . Com entrada hM i, A computa
da seguinte maneira, onde definimos n = |hM i|:
1. Calcula g(n).
2. Simula um passo de M com entrada hM i, mantendo contadores do n
umero de passos
t e do total de espaco s utilizados ate o momento por M .
3. Computa f (t, s). Se f (t, s) > g(n), rejeita a entrada.
4. Verifica se t > ng(n)2g(n) . Se esse for o caso, rejeita a entrada.
5. Se este for o u
ltimo passo de M , entao A aceita a entrada se e somente se M aceita,
caso contrario A rejeita a entrada.
3.2. Um Teorema Geral de Hierarquia
47
6. Retorna para o passo 2.
O passo 4 e necessario pois, dependendo da funcao f , a maquina M pode entrar em

um laco infinito enquanto usa uma quantidade finita de espaco, mantendo o valorde f (t, s)
constante. Primeiro provaremos que L(A) = Lf,g . Depois limitaremos a f -complexidade
de A.
Lema 3.19. Se a maquina M termina sua computacao com a entrada hM i, ent
ao a
palavra hM i nao e rejeitada por A no passo 4.
Demonstracao. Suponha que hM i seja rejeitada por A no passo 4. Como hM i nao foi
rejeitada no passo 3, sabemos que f (t, s) g(n). Se s > g(n), entao temos claramente
t > g(n), e portanto f (t, s) > g(n), uma vez que f e uma medida de complexidade natural.
Por isso, s g(n). Por esse motivo nao existem mais do que ng(n)2g(n) configuracoes
possveis para a maquina M com entrada hM i. Porem, a rejeicao no passo 4 requer
t > ng(n)2g(n) . Isso mostra que se A rejeita hM i no passo 4, entao M repete alguma
configuracao e portanto nunca termina sua computacao com a entrada hM i, fato que
contradiz a hipotese inicial do nosso lema.
Continuando com a prova do teorema, suponha que hM i Lf,g . Em particular, isso
significa que M termina sua computacao com a entrada hM i. Portanto, o lema anterior
implica que hM i nao e rejeitada por A no passo 4. Como f-tsM (hM i) g(n) e f e
nao-decrescente, temos que hM i nao e rejeitada por A no passo 3. Portanto, a simulacao
termina no passo 5 e, como M aceita hM i, o mesmo faz A. Isso prova que hM i L(A).
Agora suponha que hM i L(A). Entao hM i e aceita por A no passo 5, e por isso M
tambem aceita hM i. Como hM i nao e rejeitada por A no passo 3, podemos concluir que
f-tsM (hM i) g(|hM i|). Por esse motivo, hM i Lf,g . Logo segue que L(A) = Lf,g .
A partir de agora vamos analisar a simulacao realizada no passo 2. A maquina A
divide sua fita em 7 trilhas (considere as celulas da fita divididas modulo 7), organizadas
da seguinte maneira:
A
A
A
A
A
A
A
trilha
trilha
trilha
trilha
trilha
trilha
trilha
1 guarda g(n).
2 armazena ng(n)2g(n) .
3 e responsavel polo contador t.
4 contem o contador s.
5 e usada para computar f (t, s).
6 guarda o codigo de M e seu estado atual.
7 reflete a fita de M durante sua computacao.
48
A maquina A simula a maquina de Turing M e sempre mantem a informacao de cada

trilha proxima do local que contem a celula atual lida por M (a maquina A desloca o
conte
udo das trilhas para a esquerda ou para a direita em cada passo da simulacao).
Primeiro, vamos calcular a complexidade de espaco SA (n) de A. O valor g(n) e computado em espaco SMg (n), uma vez que Mg computa g. O valor ng(n)2g(n) pode ser
facilmente computado e armazenado em espaco O(g(n)). O contador s e limitado pelo
contador t que, por sua vez, e limitado pelo valor na trilha 2. Por esse motivo, as trilhas 3
e 4 sao irrelevantes para a complexidade de espaco assintotica final. O valor f (t, s) pode
ser computado em espaco SMf (c2 g(n)), ja que os valorres t e s sao limitados assintoticamentes por g(n). A descricao de M na trilha 6 possui tamanho n e, como g(n) n, o
espaco utilizado e tambem irrelevante. Finalmente, o tamanho da trilha 7 e limitado por
g(n) (como na prova do lema 3.19). Segue que SA (n) satisfaz:

SA (n) c1 SMg (n) + g(n) + SMf (c2 g(n)) .
(3.6)
Falta somente encontrar um limitante superior para TA (n). Sabemos que A computa
g(n) em tempo TMg (n). A multiplicacao do passo 4 pode ser feita em tempo O(g(n)).
Durante a simulacao, A precisa computar f (t, s). Sempre temos s t ng(n)2g(n) + 1,
que em binario pode ser representado por O(g(n)) bits. Por isso, f (t, s) e computado em
tempo TMf (c3 g(n)), para alguma constante c3 apropriada. Em cada passo da simulacao,
as trilhas precisam ser deslocadas e alguns valores sao comparados (lembre que A mantem
o conte
udo das trilhas por perto). Isso pode ser feito em tempo proporcional ao tamanho
das trilhas, ou seja, c1 [SMg (n)+g(n)+SMf (c2 g(n)) ]. Finalmente, nao mais do que O(g(n))
passos sao simulados. Portanto, TA (n) satisfaz:

TA (n) c4 TMg (n) + g(n) TMf (c3 g(n)) + SMg (n) + g(n) + SMf (c2 g(n)) .
(3.7)
Os teoremas classicos de hierarquia de tempo e espaco podem ser derivados como

casos particulares desse teorema geral de hierarquia. Consulte os livros de Sipser [103]
e Papadimitriou [88] para ver a demonstracao individual de cada teorema de hierarquia.
Esses teoremas utilizam o conceito de funcao construtvel, definido a seguir.
Definic
ao 3.20. [Funcao Tempo-Construtvel]. Uma funcao g : N N e dita tempoconstrutvel se a funcao que mapeia 1n para a representacao binaria de g(n) pode ser
computada em tempo O(g(n)).
Definic
ao 3.21. [Funcao Espaco-Construtvel]. Uma funcao g : N N e dita espacoconstrutvel se a funcao que mapeia 1n para a representacao binaria de g(n) pode ser
computada em espaco O(g(n)).
3.3. Consequencias do Resultado Anterior
49
Observamos que a maior parte das funcoes utilizadas em complexidadecomputacional

sao construtveis no sentido das definicoes 3.20 e 3.21. Por exemplo, n5 , 2 n e n log n sao
funcoes tempo-construtveis.
Corol
ario 3.22. [Hierarquia de Tempo]. Para qualquer funcao tempo-construtvel g :
N N com g(n) n, existe uma linguagem decidvel em tempo O(g(n)2 ) que n
ao pode
ser decidida em tempo o(g(n)).
Demonstracao. Seja f (x, y) = x. Pelo teorema 3.18 e pela definicao de f , Lf,g pode ser
decidida em tempo O(TA (n)), onde TA (n) satisfaz (3.4). Tambem temos que SMg (n)
TMg (n) e TMg (n) e O(g(n)), uma vez que g e uma funcao tempo-construtvel e g(n) n.
Dada a definicao de f , podemos assumir que TMf (n) e SMf (n) sao funcoes O(n). Portanto,
Lf,g e decidvel em tempo O(g(n)2 ). Pelo teorema 3.15, Lf,g nao pode ser decidida em
tempo o(g(n)).
Corol
ario 3.23. [Hierarquia de Espaco]. Para qualquer funcao espaco-construtvel g :
N N com g(n) n, existe uma linguagem decidvel em espaco O(g(n)) que n
ao pode
ser decidida em espaco o(g(n)).
Demonstracao. Seja f (x, y) = y. Entao o teorema 3.18 pode ser aplicado para obtermos que Lf,g e uma linguagem decidvel em f -complexidade O(SA (n)), onde SA (n)
c1 [SMg (n) + g(n) + SMf (c2 g(n)) ]. Sendo g uma funcao espaco-construtvel, temos que
SMg (n) e O(g(n)), ja que g(n) n. Pela definicao de f , podemos assumir que SMf (n) e
O(n). Por isso, Lf,g pode ser decidida em espaco O(g(n)). Pelo teorema 3.15, Lf,g nao
pode ser decidida em espaco o(g(n)).
Observe que a hierarquia de espaco e mais forte que a hierarquia de tempo. Isso ocorre
porque uma quantidade de tempo assintoticamente relevante e perdida com os detalhes
da simulacao. Note que simulacoes mais eficientes produzem resultados mais fortes.
Veremos na secao 3.4 que uma situacao inesperada ocorre quando trabalhamos com
funcoes que nao sao construtveis.
3.3
Consequ
encias do Resultado Anterior
As classes de complexidade estudadas ate agora foram definidas a partir do modelo

computacional de maquinas de Turing com varias fitas. Por isso, antes de aplicarmos os
resultados da secao anterior (validos para maquinas de Turing de fita u
nica e alfabeto
binario) precisamos traduz-los para esse modelo computacional. Para mostrar a generalidade dos resultados obtidos, vamos discutir primeiramente o que ocorre quando os
modelos computacionas envolvidos sao arbitrarios.
50
Um fato importante verificado para os modelos estudados em computacao e a equivalencia em termos de poder computacional entre eles. Esse fato e conhecido como a Tese
de Church-Turing. Isso significa que, dados dois modelos computacionais suficientemente
poderosos C1 e C2 , e possvel converter uma maquina do primeiro modelo em uma maquina
equivalente do segundo modelo, i.e., capaz de decidir a mesma linguagem. Alem disso,
para todos os modelos fisicamente implementaveis conhecidos, o tempo de execucao da
maquina convertida e no maximo polinomialmente maior do que o tempo de execucao da
maquina original. Por isso, se C1 e C2 sao dois modelos computacionais arbitrarios, existe
um polinomio p12 (x) tal que se uma linguagem L pode ser decidida em tempo O(t(n)) no
modelo C1 , entao L pode ser decidida em tempo O(p12 (t(n))) no modelo computacional
C2 .
Definic
ao 3.24. Seja C um modelo computacional arbitrario. O conjunto de linguagens
decidveis em tempo determinstico O(t(n)) no modelo computacional C sera denotado por
DTIMEC (t(n)).
Lema 3.25. Seja t : N N uma funcao arbitraria. Temos entao que:
(i) Se L DTIMEC1 (t(n)), entao L DTIMEC2 (p12 (t(n))).
(ii) Se L
/ DTIMEC1 (p21 (t(n))), entao L
/ DTIMEC2 (t(n)).
As funcoes p12 (x) e p21 (x) sao os polinomios associados ao custo computacional adicionado na conversao entre as maquinas dos modelos computacionais C1 e C2 .
Demonstracao. A demonstracao de (i) e imediata e a demonstracao de (ii) segue pela
contrapositiva.
Esse fato simples mostra que a existencia de hierarquias de complexidade e uma propriedade compartilhada por todos os modelos computacionais.
Considere a partir de agora que C1 e o modelo computacional de maquinas de Turing
de fita u
nica com alfabeto binario e denote por C2 o modelo computacional de maquinas de
Turing arbitrarias. Portanto, temos daqui em diante que DTIMEC2 (t(n)) = DTIME(t(n)).
imediato que p12 (x) = x, uma vez que C1 e um caso particular de C2 . Segue do proximo
E
resultado que podemos tomar p21 (x) = x2 .
Teorema 3.26. Seja M1 uma maquina de Turing que decide uma linguagem L em tempo
O(t(n)). Entao existe uma maquina de Turing de fita u
nica e alfabeto binario que decide
2
L em tempo O(t(n) ).
Demonstracao. A prova desse resultado segue a partir de uma simulacao similar àquela
utilizada na prova do lema 3.3, onde varias fitas sao armazenadas em uma u
nica fita da
maquina simuladora.
3.4. O Teorema da Lacuna
51
Temos finalmente tudo que precisamos para separar algumas classes de complexidade
importantes.
Teorema 3.27. P 6= EXP.
Demonstracao. Observe primeiramente que t(n) = 2n/2 e uma funcao tempo-construtvel
em maquinas de Turing de fita u
nica. Portanto, pelo corolario 3.22, temos a inclusao
n/4
propria de classes DTIMEC1 (2 ) ( DTIMEC1 (2n ). Alem disso, segue a partir do lema
3.25 que:
P DTIME(2n/8 ) DTIMEC1 (2n/4 ) ( DTIMEC1 (2n ) DTIME(2n ) EXP,
como queramos demonstrar.
As mesmas ideias podem ser utilizadas para separar outras classes de complexidade
importantes. O proximo resultado segue a partir dos teoremas de hierarquia de modo
analogo.
Definic
ao 3.28. [Classe de Complexidade E].
S
E = c1 DTIME(2cn ).
Teorema 3.29.
(i) PSPACE 6= EXPSPACE.
(ii) E 6= EXP.
(iii) P 6= E.
Alem disso, o argumento utilizado na demonstracao do teorema 3.6 pode ser usado
para provar que NP 6= E.
3.4
O Teorema da Lacuna
Veremos nesta secao que os teoremas de hierarquia podem nao ser validos quando
utilizamos funcoes nao-construtveis. Por exemplo, existem funcoes t(n) nao-triviais tais
que DTIME(t(n)) = DTIME(2t(n) ). Assim como demonstramos um teorema de hierarquia
um pouco mais geral, vamos provar uma versao mais abstrata do resultado conhecido como
Teorema da Lacuna (Borodin [16]).
Definic
ao 3.30. Uma linguagem L pertence à classe COMPLEXf (g(n)) se existe uma
maquina de Turing A que decide L e, para todo inteiro n, temos que f-TSA (n) g(n).
52
Teorema 3.31. [Teorema da Lacuna]. Seja f uma medida de complexidade natural.

Existe uma funcao computavel g : N N com g(n) n tal que se L COMPLEXf (2g(n) ),
entao L pode ser decidida em f -complexidade O(g(n)).
Demonstracao. Considere uma ordenacao lexicografica das maquinas de Turing: M0 , M1 ,
M2 , . . . . Para i, k 0, definimos que o predicado P (i, k) e verdadeiro se:
Para todo j, 0 j i, temos que Mj com qualquer entrada x de tamanho i
satisfaz f -tsMj (x) < k ou entao temos f -tsMj (x) > 2k ou f -tsMj (x) e indefinido
(Mj pode computar indefinidamente com a entrada x).
Note que P (i, k) e uma propriedade decidvel atraves de uma simulacao analoga à apresentada na demonstracao do teorema 3.18.
Continuamos com a definicao da funcao g. Fixe um inteiro i 0. Como o n
umero de
maquinas de Turing Mj com j i e o n
umero de palavras x com |x| = i sao finitos, existe
uma quantidade finita de pares (Mj , x) satisfazendo essas condicoes. Alem disso, cada
par (Mj , x) so pode tornar P (i, k) falso para uma quantidade finita de inteiros k. Por
isso, deve existir um inteiro l i tal que P (i, l) e verdadeiro. Selecione o menor desses
inteiros e defina g(i) = l. Como o predicado P e decidvel, g e uma funcao computavel.
Por construcao, g(i) i e P (i, g(i)) e verdadeiro, para todo i.
Suponha que L COMPLEXf (2g(n) ). Entao L e decidida por alguma maquina de
Turing Mj em f -complexidade 2g(n) . Considere agora qualquer palavra x com |x| j.
Por construcao, P (|x|, g(|x|)) e verdadeiro. Temos que j |x|, portanto para a maquina
Mj : f -tsMj (x) < g(|x|) ou f -tsMj (x) > 2g(|x|) ou f -tsMj (x) e indefinido. Como Mj decide
L em f -complexidade 2g(n) , segue que f -tsMj (x) < g(|x|). Como o conjunto de palavras
de tamanho menor do que j e finito, L pode ser decidida em f -complexidade O(g(n)).
Observe que podemos trocar a funcao 2n utilizada no teorema por qualquer outra
funcao computavel nao-descrescente.
Quando tomamos f como sendo uma das funcoes de projecao, obtemos os teoremas
classicos da lacuna para tempo e espaco.
Corol
ario 3.32. [Teorema da Lacuna para Tempo]. Existe uma funcao computavel t :
N N tal que, para toda linguagem L {0, 1}? , se L pode ser decidida em tempo 2t(n) ,
entao L pode ser decidida em tempo O(t(n)).
Corol
ario 3.33. [Teorema da Lacuna para Espaco]. Existe uma funcao computavel s :
N N tal que, para toda linguagem L {0, 1}? , se L pode ser decidida em espaco 2s(n) ,
entao L pode ser decidida em espaco O(s(n)).
3.5. A Hierarquia Nao-Determinstica
3.5
53
A Hierarquia N
ao-Determinstica
Nosso proximo objetivo e obter resultados para classes nao-determinsticas similares

aos obtidos nas secoes 3.2 e 3.3.
Existe um obstaculo fundamental impedindo que a demonstracao do teorema de hierarquia determinstico seja traduzida para o caso nao-determinstico. Observe que o fecho
por complementacao de linguagens existente no caso determinstico e essencial para a diagonalizacao ocorrida na prova do teorema 3.15. Porem, nao esperamos em geral que o
complemento de uma linguagem decidida por uma MTND seja decidida por outra MTND
de mesma complexidade de tempo. Em particular, muitos pesquisadores acreditam que
NP 6= coNP. Apesar disso, o complemento de uma linguagem decidida por um MTND
em tempo f (n) pode ser decidida em tempo determinstico 2f (n) f (n) atraves da enumeracao de todas as escolhas nao-determinsticas possveis. Felizmente, esse fato pode ser
explorado atraves de um argumento de diagonalizacao um pouco mais elaborado.
Teorema 3.34. [Hieraquia de Tempo Nao-Determinstica]. Sejam f, g : N N func
oes e
assuma que f e uma funcao tempo-construtvel nao-decrescente com f (n + 1) log f (n + 1)
sendo o(g(n)). Entao NTIME(f (n)) ( NTIME(g(n)).
Demonstracao. Para nao discutirmos mais uma vez detalhes de simulacao, vamos apenas
esbocar a demonstracao desse resultado. Veja a secao de referencias do captulo para mais
detalhes.
Considere uma ordenacao lexicografica das MTNDs: M0 , M1 , M2 , . . . . Para cada
MTND Mi vamos associar um intervalo Ii = [(i) + 1, . . . , (i + 1)], onde : N N e
uma funcao crescente que depende de f a ser determinada posteriormente.
Para provar o resultado, vamos exibir uma MTND D com complexidade de tempo
O(g(n)) cuja linguagem L(D)
/ NTIME(f (n)). Para isso, construiremos D de forma
que, para todo inteiro i, se Mi computa em tempo O(f (n)) entao existe k Ii tal que
Mi (1k ) 6= D(1k ).
Isso pode ser conseguido se simularmos a maquina Mi de um modo mais inteligente e
entao negarmos a sua resposta. Porem, como discutido no incio da secao, o grande desafio
e negar a resposta de Mi sem ultrapassar o limite de complexidade O(g(n)). O argumento
que vamos apresentar e conhecido como metodo da diagonalizacao atrasada. Lembre que
queremos provar que se Mi e uma maquina nao-determinstica que computa em tempo
O(f (n)), entao L(Mi ) 6= L(D). Em outras palavras, D nao precisa se preocupar com o
seu comportamento em relacao à maquinas de Turing que computam por mais do que
cerca de f (n) passos.
Seja Mi uma MTND que computa em tempo O(f (n)). A maquina D utiliza o seu
nao-determinismo para simular Mi por cerca de f (k + 1) passos, de forma a obter: k
Ii \{(i + 1)}, D(1k ) = Mi (1k+1 ) (i). Porem, observe que ainda nao definimos o valor
54
exatamente aqui que diagonalizamos: com entrada 1(i+1) , D simula

de D(1(i+1) ). E
deterministicamente a maquina Mi com entrada 1(i)+1 por cerca de f ((i + 1)) passos e
nega a sua resposta (ii). Se D computar dessa forma, nao podemos ter L(D) = L(Mi ).
Caso contrario, seguiria a partir disso e de (i) que D e Mi aceitam todas as palavras
unarias formadas por uma sequencia de 1s com tamanho em Ii ou rejeitam todas essas
palavras. No entanto, segue por (ii) que D aceita 1(i+1) se e somente se Mi rejeita 1(i)+1 .
Isso prova que L(D)
/ NTIME(f (n)).
Finalmente, para mostrarmos que L(D) NTIME(g(n)), notamos que:
(1) Dada uma entrada na forma 1k , D descobre qual maquina de Turing simular atraves
do calculo da funcao (k). Isso pode ser feito em tempo O(g(n)), pois pode ser definida
de forma que sua complexidade dependa essencialmente da complexidade de f , que por
sua vez e uma funcao tempo-construtvel em o(g(n)) passos;
(2) A simulacao utilizada em (i) pode ser feita no tempo desejado, pois f (n+1) log f (n+1)
e o(g(n))1 ;
(3) A simulacao determinstica que ocorre em (ii) nao ultrapassa o limite O(g(n)), pois
a funcao (n) garante que a entrada 1(i)+1 para a maquina Mi e muito menor do que a
entrada 1(i+1) da maquina D. Por exemplo, podemos definir essa funcao como: (1) = c
e (n+1) = 22f ((n)) , onde c e uma constante que depende dos detalhes de implementacao
de D.
Teorema 3.35. NP 6= NEXP.
2
Demonstracao. Segue do teorema anterior que NP NTIME(2n ) ( NTIME(2n ) NEXP.

Observe que classes como P, NP e PSPACE nao podem ser separadas pelos teoremas
de hierarquia apresentados. Esses resultados nao relacionam classes de complexidade que
envolvem recursos diferentes. Apesar disso, podemos combinar os resultados anteriores
para provar alguns teoremas interessantes.
Teorema 3.36.
(i) P 6= NP ou NP 6= EXP.
(ii) PSPACE 6= EXP ou EXP 6= EXPSPACE.
1
E possvel simular t(n) passos de uma maquina de Turing em tempo t(n) log t(n). Consulte a secao
de referencias deste captulo para mais detalhes.
3.6. O Metodo da Completude
55
(iii) NP 6= EXP ou EXP 6= NEXP.

Demonstracao. A demonstracao desses resultados segue por teoria de conjuntos elementar
a partir dos teoremas 3.11, 3.27, 3.29 e 3.35.
3.6
O M
etodo da Completude
Na secao 2.5 vimos que os problemas NP-completos sao os mais difceis da classe NP.
Uma propriedade fundamental da nocao de completude e que se demonstrarmos que um
problema completo esta em uma classe inferior, entao ocorre um colapso de classes. Por
isso, caso seja provado que P 6= NP, sabemos que nenhum problema NP-completo admite
algoritmos eficientes.
Os teoremas de hierarquia implicam que diversas classes de complexidade sao distintas.
Por exemplo, vimos que P 6= EXP. Definindo adequadamente a nocao de completude para
a classe EXP, podemos obter que problemas EXP-completos nao podem ser resolvidos em
tempo polinomial. Interessantemente, muitos problemas praticos acabam se mostrando
completos para alguma classe de complexidade. Isso nos da uma compreensao muito boa
da dificuldade do problema sendo estudado.
Definic
ao 3.37. [Completude]. Seja R uma classe de complexidade. Dizemos que uma
linguagem L {0, 1}? e R-completa se:
(i) L R;
(ii) Para toda linguagem L0 R, temos L0 p L.
Observe que as classes de complexidade EXP, PSPACE, coNP, coNEXP e EXPSPACE
sao fechadas por reducao de tempo polinomial. Consequentemente, se provarmos que um
problema completo de uma certa classe de complexidade A pertence à classe B, temos
A B. Conversamente, se A * B entao problemas completos da classe A nao pertencem
a` classe de complexidade B.
Uma construcao semelhante a que aparece na demonstracao do teorema 2.22 pode
ser usada para exibir linguagens completas para diversas dessas classes. Embora esses
problemas nao sejam muito u
teis, problemas completos naturais podem facilitar certas
demonstracoes envolvendo classes de complexidade. Veremos a seguir como a nocao de
completude pode ser usada para classificar a dificuldade computacional de alguns problemas de interesse pratico.
Uma expressao regular e uma forma sucinta de representar palavras (sequencias de caracteres) que satisfazem um certo padrao. Por exemplo, uma palavra satisfaz a expressao
regular A? bA? se ela e formada por uma sequencia arbitraria de As, seguido por um b, e
56
depois por mais uma sequencia de As. Outro exemplo e a expressao regular {c b}arro,
satisfeita pelas palavras carro e barro. Portanto, uma expressao regular e uma palavra
bem-definida e o conjunto de palavras que satisfazem uma certa expressao regular e uma
possvel combinar as operacoes basicas ?, e a concatenacao de smbolos
linguagem. E
para produzir regras que codificam linguagens sofisticadas.
Expressoes regulares sao usadas por diversos utilitarios, tais como editores de texto
e interpretadores, para manipular texto baseado em padroes. Por exemplo, pode-se usar
uma expressao regular para garantir que o dado digitado por um usuario e um endereco
web valido. Outro uso importante de expressoes regulares e a filtragem de informacao em
bancos de dados textuais. Vamos definir a seguir o conjunto de palavras que representam expressoes regulares validas. Por simplicidade, vamos considerar apenas o alfabeto
binario.
Definic
ao 3.38. [Expressoes Regulares]. O conjunto de expressoes regulares pode ser
definido indutivamente atraves das seguintes regras: (1) os smbolos 0 , 1 e sao expressoes
regulares; (2) se 1 e 2 sao expressoes regulares, entao 1 2 , 1 2 e 1? sao expressoes
regulares. O significado de uma expressao regular e uma linguagem definida indutivamente
da seguinte maneira: L(0) = {0}, L(1) = {1}, L() = , L(1 2 ) = L(1 )L(2 ) = {xy :
x L(1 ), y L(2 )}, L(1 2 ) = L(1 ) L(2 ), e L(1? ) = L(1 )? . Os operadores sao
aplicados de acordo com a ordem de precedencia anterior. Finalmente, dizemos que duas
expressoes regulares 1 e 2 sao equivalentes se L(1 ) = L(2 ).
Um importante problema computacional e decidir se duas expressoes regulares sao
equivalentes. Atraves de algumas modificacoes na definicao de expressao regular, essa
tarefa fornece um grande n
umero de problemas completos:
(1) O problema de decidir se duas expressoes regulares sao equivalentes e PSPACEcompleto.
(2) Uma expressao regular e livre de estrela se nao possui ocorrencias do operador ? .
Decidir se duas expressoes regulares livres de estrela sao equivalentes e um problema
coNP-completo.
(3) Suponha que adicionemos o operador 2 (elevar ao quadrado) no conjunto de operadores de expressoes regulares, de forma que L(2 ) = L()L(). Decidir se duas expressoes
regulares livres de estrela e com o operador 2 sao equivalentes e um problema coNEXPcompleto.
(4) Suponha que os operadores ? e 2 sejam permitidos. Entao o problema da equivalencia de expressoes regulares se torna EXPSPACE-completo. Por isso, sabemos pelo
57
teorema 3.29 que esse problema nao pode ser resolvido de forma eficiente.
(5) Alem disso, podemos adicionar um operador de negacao a`s expressoes regulares,
de forma que L() = {0, 1}? \L(). Nesse caso, o problema de equivalencia nao pode
ser resolvido por nenhum algoritmo determinstico com tempo de execucao limitado por
uma torre de exponenciais de altura constante.
A prova desses resultados pode ser obtida em Meyer e Stockmeyer [79, 80]. Muitos outros
problemas completos e demonstracoes de completude podem ser obtidos no livro de Du e
Ko [33].
Os resultados provados neste captulo mostram que alguns problemas computacionais
nao podem ser resolvidos de modo eficiente. Podemos demonstrar isso porque tais problemas sao completos em suas respectivas classes de complexidade. Entretando, veremos na
secao 4.5 que e bem provavel que diversos problemas computacionais interessantes nao sejam completos. Um grande desafio para os pesquisadores em complexidade computacional
e descobrir metodos capazes de provar que problemas nessa situacao sao computacionamente difceis. Infelizmente, os argumentos utilizados neste captulo provavelmente nao
sao suficientes para isso. Discutiremos em profundidade os limites do metodo de diagonalizacao no captulo 5.
3.7
Refer
encias Adicionais
As demonstracoes dos teoremas de hierarquia e da lacuna apresentadas aqui podem

ser obtidas no artigo de Oliveira e Moura [87]. O artigo de Blum [12] introduz uma
nocao muito mais geral de medida de complexidade. Recomendamos tambem o artigo de
Seiferas [98] para uma discussao sobre resultados em complexidade que sao independentes
do modelo computacional em consideracao.
O teorema de hierarquia nao-determinstico foi provado inicialmente por Cook [27].
Uma versao mais forte desse resultado aparece no artigo de Seiferas et al. [99]. A demonstracao apresentada na secao 3.5 e devida a` Zak [116].
interessante notar que, embora ocorra uma perda quadratica de tempo na simulacao
E
de maquinas de Turing de varias fitas por uma maquina de fita u
nica, e possvel simular
maquinas arbitrarias em apenas duas fitas em tempo T (n) log T (n), onde T (n) e a complexidade de tempo da maquina simulada. Veja o artigo de Hennie e Stearns [56] para
mais detalhes.
O artigo de Fortnow [39] descreve algumas aplicacoes mais recentes do metodo de
diagonalizacao. No mesmo artigo, o autor sugere a possibilidade de usar diagonalizacao
para separar a classe NP de classes mais fracas do que P. Como veremos no captulo 5, e
58
improvavel que o metodo de diagonalizacao sozinho seja capaz de separar as classes P e

NP.
Recomendamos a leitura de outro artigo de Fortnow [40] para uma discussao sobre
classes de complexidade mais poderosas que NP e problemas completos para essas classes.
A discussao sobre o problema da equivalencia para expressoes regulares e motivada por
um exerccio que aparece no livro de Papadimitriou [88]. A demonstracao de completude
da versao EXPSPACE-completa do problema pode ser obtida no livro de Sipser [103].
Captulo 4
O Problema P vs NP em
Profundidade
May the force of P and NP be with you.
Sanjeev Arora.
Neste captulo vamos discutir alguns topicos mais avancados relacionados com
o problema P vs NP. Inicialmente, veremos como a hierarquia polinomial generaliza a definicao das classes de complexidade P e NP. Vamos mostrar tambem
que algoritmos muito eficientes em tempo e espaco nao sao capazes de decidir
a linguagem SAT. Discutiremos em seguida algumas propriedades estruturais
das linguagens em NP. Por u
ltimo, demonstraremos que existem algoritmos
assintoticamente otimos para todos os problemas da classe NP.
4.1
A Hierarquia Polinomial
Na secao 3.1 mostramos que NP PSPACE. Vamos a partir de agora explorar algumas
classes de complexidade situadas entre NP e PSPACE.
A Hierarquia Polinomial (PH) foi definida inicialmente por Meyer e Stockmeyer [79,
105], a partir de uma generalizacao das classes P e NP. Muitos resultados importantes
em complexidade computacional estao relacionados com a hipotese de que a hierarquia
polinomial nao colapsa em nenhum de seus nveis.
Diversos problemas naturais tem complexidade de tempo situada em PH. Por exemplo,
seja (x1 , . . . , xn ) uma formula proposicional e f : {0, 1}n {0, 1} a funcao computada
por essa formula. Seria a formula que computa a funcao f e em cuja descricao ocorrem
59
60
Captulo 4. O Problema P vs NP em Profundidade
o menor n
umero possvel de conectivos? Por definicao, uma formula proposicional e
satisfatvel se e somente se existe uma atribuicao que a torne verdadeira. Por outro lado,
uma formula e a menor possvel se e somente se para toda formula proposicional 0
onde ocorrem menos conectivos, existe uma atribuicao ~x tal que (~x) 6= 0 (~x). Observe
que essa combinacao de quantificadores aumenta significativamente nossa capacidade de
expressar problemas computacionais. Vejamos mais um exemplo.
Exemplo 4.1. [Jogadas Finais em um Jogo Arbitrario]. Consideramos neste exemplo um
jogo de tabuleiro entre dois jogadores com as seguintes propriedades:
(i) Dada uma descricao C de um tabuleiro do jogo, e possvel verificar de modo eficiente
todas as proximas jogadas possveis, ou seja, sabemos verificar se um tabuleiro C 0
pode ser obtido a partir de C com uma u
nica jogada;
(ii) Os jogadores alternam as jogadas;
(iii) Existe uma maquina de Turing eficiente M que, ao receber como entrada um tabuleiro C0 e tabuleiros C1 , . . . , Ck , aceita a entrada hC0 , C1 , . . . , Ck i se e somente se:
(1) cada tabuleiro pode ser obtido a partir do tabuleiro anterior conforme descrito
no item (i); (2) os jogadores alternam as jogadas; (3) algum tabuleiro Ci determina
a vitoria do primeiro jogador.
Observe que certos jogos de tabuleiro classicos como dama e xadrez satisfazem as propriedades anteriores. No entanto, jogos muito mais gerais podem ser codificados pela maquina
de Turing M .
Considere agora o seguinte problema computacional. Dado um tabuleiro C, o primeiro
jogador pode ganhar o jogo nas proximas k jogadas? Em outras palavras, existe uma jogada
do primeiro jogador que leva a um tabuleiro valido C1 tal que, para toda jogada do segundo
jogador que leva a um tabuleiro valido C2 tal que, existe um jogada do primeiro jogador . . .
de forma que em no maximo k jogadas o jogo e vencido pelo primeiro jogador? Isso e o
mesmo que perguntar se existe uma estrategia vencedora para o primeiro jogador que pode
ser aplicada às proximas k jogadas. Esse problema pode ser representado pela seguinte
linguagem:
Lk = {hCi {0, 1}? : C1 C2 . . . Qk Ck M (C, C1 , . . . , Ck ) = 1},
onde Qi e o quantificador ou de acordo com a paridade do inteiro k.
Intuitivamente, esse problema e muito mais difcil do que problemas em NP. Por
exemplo, tomando k = 1 e considerando M como sendo um verificador eficiente para SAT,
podemos considerar uma formula proposicional como sendo um jogo em que o primeiro
jogador vence se consegue encontrar uma atribuicao que satisfaca a formula de entrada.
4.1. A Hierarquia Polinomial
61
Definic
ao 4.2. [Hierarquia Polinomial]. Para todo inteiro k 0, dizemos que uma
linguagem L pertence à classe pk (k-esimo nvel da hierarquia polinomial) se existe uma
maquina de Turing M que computa em tempo polinomial e um polinomio q(.) tal que
x L w1 {0, 1}q(|x|) w2 {0, 1}q(|x|) . . . Qk wk {0, 1}q(|x|) M (x, w1 , . . . , wk ) = 1,
onde Qk denota ou se k for par ou mpar, respectivamente.
Alem disso, definimos pk = copk = {L : L pk }. Finalmente, definimos a hierarS
quia polinomial como sendo a classe de complexidade PH = k0 pk .
Novamente, a restricao de que toda palavra wi tenha tamanho exato q(|x|) nao e uma
limitacao. Basta que as palavras envolvidas sejam polinomialmente limitadas, uma vez
que sempre podemos obter uma maquina de Turing equivalente que opera de acordo com
as restricoes de tamanho da definicao anterior. Utilizaremos esse fato implicitamente a
partir de agora.
A linguagem Lk discutida no exemplo 4.1 pertence a` classe pk . Por isso, temos que
Lk esta em pk . Considere a seguir jogos em que a vitoria sera determinada nas proximas
k jogadas (ou seja, se M (C, C1 , . . . , Ck ) = 0 entao o segundo jogador vence o jogo).
Negando a definicao de Lk , obtemos que Lk representa o problema de verificar se existe
uma estrategia vencedora para o segundo jogador para as proximas k jogadas.
Observe que P = p0 = p0 , NP = p1 e coNP = p1 . Alem disso, por definicao, se
L pk entao L pk , ou seja:
onde Qk denota ou se k for par ou mpar, respectivamente. Portanto, negando os dois
lados da equivalencia anterior, obtemos que:
onde dessa vez Qk denota ou se k for mpar ou par, respectivamente. Seja M 0
uma maquina de Turing que aceita sua entrada se e somente se M rejeita sua entrada.
Claramente:
x L w1 {0, 1}q(|x|) w2 {0, 1}q(|x|) . . . Qk wk {0, 1}q(|x|) M 0 (x, w1 , . . . , wk ) = 1.
Isso mostra que, alterando a disposicao dos quantificadores, podemos obter uma definicao
alternativa para a classe pk .
Utilizando a observacao anterior, note que para todo inteiro k 0 temos pk pk+1
pk+2 (o novo quantificador nao altera a validade da expressao se desprezarmos a palavra de
S
entrada adicional). Portanto, PH = k0 pk . Similarmente, e facil provar que pk pk+1
e que pk pk+1 .
62
A hierarquia polinomial e definida para problemas de decisao, ou seja, linguagens. No

entanto, podemos associar um problema de busca à maquina de Turing M utilizada na
possvel adaptar a prova do teorema
definicao de pk (como discutido na secao 2.3). E
p
2.15 para mostrar que se k = P, entao podemos encontrar eficientemente uma palavra
w1 como na definicao 4.2. De forma mais geral, dados i certificados () e i palavras ()
anteriores, podemos encontrar eficientemente o (i + 1)-esimo certificado.
Como discutido anterioremente, ainda e um problema em aberto provar que a hierarquia polinomial possui infinitos nveis distintos.
Quest
ao em Aberto 4.3. Existe um inteiro k 0 tal que PH = pk ?
Veremos nos proximos teoremas que o colapso entre dois nveis adjacentes provoca o
colapso da hierarquia polinomial.
Lema 4.4. Para todo inteiro k 0, se pk+1 = pk entao pk+1 = pk .
Demonstracao. Assuma que L pk+1 . Entao L pk+1 pk . Por definicao, isso significa
que L pk , como queramos demonstrar.
Teorema 4.5. [Colapso Vertical].
Para todo inteiro k 0, se pk+1 = pk entao PH = pk .
Demonstracao. Assuma que pk+1 pk . Vamos provar que pk+2 pk+1 . O resultado
segue por inducao, pois teramos entao pj pk , para todo inteiro j k.
Seja L pk+2 , ou seja, existe uma maquina de Turing ML de tempo polinomial e um
polinomio q(.) tal que
x L w1 w2 w3 . . . Qk+2 wk+2 ML (x, w1 , . . . , wk+2 ) = 1,
onde wi {0, 1}q(|x|) para todo 1 i k + 2. Considere agora a linguagem
L0 = {hx, w1 i : |w1 | = q(|x|) e w2 w3 . . . Qk+2 wk+2 ML (x, w1 , . . . , wk+2 ) = 1}.
imediato que x L se e somente se existe w1 de tamanho q(|x|) tal que hx, w1 i L0 (1).
E
Alem disso, segue a partir da definicao de L0 que L0 pk+1 . Portanto, pelo lema 4.4 temos
que L0 pk . Em outras palavras, existe uma maquina de Turing ML0 de tempo polinomial
e um polinomio q 0 (.) tais que
hx, w1 i L0 |w1 | = q(|x|) e w2 w3 . . . Qk wk+1 ML0 (hx, w1 i, w2 , . . . , wk+1 ) = 1 (2),
0
q(|x|)
i|)
onde wi {0, 1}q (|hx,1
para todo 2 i k + 1. Combinando (1) e (2), podemos
obter um polinomio p(.) adequado e modificar a maquina ML0 de forma que:
x L w1 w2 . . . Qk+1 wk+1 ML0 (x, w1 , . . . , wk+1 ) = 1,

onde wi {0, 1}p(|x|) para 1 i k + 1. Isso completa a prova de que L pk+1 .
63
Teorema 4.6. [Colapso Horizontal].

Para todo inteiro k 0, se pk = pk entao PH = pk .
Demonstracao. Vamos provar que se pk = pk , entao pk+1 pk . O resultado segue pelo
teorema anterior, uma vez que pk pk+1 .
Seja L pk+1 , ou seja, existe uma maquina de Turing ML de tempo polinomial e um
polinomio q(.) tal que
x L w1 w2 w3 . . . Qk+1 wk+1 ML (x, w1 , . . . , wk+1 ) = 1,
onde wi {0, 1}q(|x|) para todo 1 i k + 1. Considere agora a linguagem
L0 = {hx, w1 i : |w1 | = q(|x|) e w2 w3 . . . Qk+1 wk+1 ML (x, w1 , . . . , wk+1 ) = 1}.
imediato que x L se e somente se existe w1 de tamanho q(|x|) tal que hx, w1 i L0 (1).
E
Alem disso, segue a partir da definicao de L0 que L0 pk . Portanto, por hipotese, temos
que L0 pk . Em outras palavras, existe uma maquina de Turing eficiente ML0 e um
polinomio q 0 (.) tal que:
hx, w1 i L0 u1 u2 u3 . . . Qk uk ML0 (hx, w1 i, u1 , . . . , uk ) = 1 (2),
0
q(|x|)
i|)
onde ui {0, 1}q (|hx,1
para todo 1 i k. Seja p(.) um polinomio tal que p(n) =
0
n q(n)
q(n)+q (|h1 , 1 i|), para todo inteiro n. Combinando (1) e (2) e modificando a maquina
ML0 , obtemos que existe uma maquina de Turing eficiente M tal que:
x L y1 {0, 1}p(|x|) y2 {0, 1}p(|x|) . . . Qk yk {0, 1}p(|x|) M (x, y1 , . . . , yk ) = 1.

Portanto, L pk , como queramos demonstrar.
Corol
ario 4.7.
(i) P = NP se e somente se PH = P.
(ii) NP = coNP se e somente se PH = NP.
Demonstracao. A prova desses resultados segue imediatamente a partir dos teoremas anteriores e da observacao de que P = p0 , NP = p1 e coNP = p1 .
Portanto, para provar que P 6= NP e suficiente demonstrar que existe um inteiro k 0
tal que pk ( pk+1 .
muito improvavel que possamos resolver os problemas em p (para k arbitrario)
E
k
de modo eficiente. Logo, o corolario 4.7 fornece uma evidencia forte de que P 6= NP. No
entanto, assim como ocorre com o problema P vs NP, apenas simulacao e diagonalizacao
nao sao suficientes para resolver o problema em aberto 4.3. Veremos o principal motivo
por tras disso no captulo 5.
O proximo resultado (em conjunto com o teorema 3.11) mostra como a hierarquia
polinomial se relaciona com as classes de complexidade discutidas anterioremente.
64
Lema 4.8. PH PSPACE.

Demonstracao. Seja L PH. Entao existe uma maquina de Turing M de tempo polinomial e um polinomio q(.) de acordo com a definicao 4.2. Vamos exibir um algoritmo
recursivo A que decide L em espaco polinomial.
Com entrada x, A computa em cada nvel da recursao da seguinte maneira: (1) verifica se a profundidade da recursao e par ou mpar; (2) gera todas as palavras possveis de
tamanho q(|x|); (3) realiza 2q(|x|) chamadas recursivas; (4) retorna a conjuncao ou disjuncao do resultado dessas chamadas de acordo com a paridade verificada em (1). No caso
base, nosso algoritmo recursivo invoca a maquina de Turing M com a entrada x e as k
palavras geradas nas etapas anteriores. Note que, por construcao, esse algoritmo decide
a linguagem L.
Observe que so precisamos armazenar em cada um dos k nveis da recursao qual foi a
u
ltima palavra gerada e um bit adicional que guarda o resultado intermediario da operacao
realizada em (4). Isso pode ser feito pois podemos invocar o algoritmo recursivamente
logo apos a geracao da proxima palavra. Finalmente, uma vez que M computa em tempo
polinomial (e portanto em espaco polinomial), o algoritmo utiliza espaco polinomial no
tamanho da entrada, ou seja, L PSPACE.
O teorema anterior tambem pode ser provado, por inducao em k, se utilizarmos a
linguagem L0 obtida a partir de L da mesma forma como foi feito nas demonstracoes anteriores. Por exemplo, por hipotese de inducao, existe uma maquina de espaco polinomial
que decide L0 . Porem, sabemos que x L se e somente se existe w1 tal que hx, w1 i L0 .
Essa u
ltima condicao pode ser facilmente verificada em espaco polinomial.
Quest
ao em Aberto 4.9. PH = PSPACE ?
Vamos analisar melhor essa relacao de classes apos estudarmos a existencia de problemas completos para PH e suas subcasses pk .
Definic
ao 4.10. [Problemas Completos em PH]. Dizemos que uma linguagem L {0, 1}?
p
e k -completa se L pk e toda linguagem em pk e Karp-redutvel à L. Analogamente,
dizemos que L e PH-completa se L PH e toda linguagem em PH e Karp-redutvel à L.
Teorema 4.11. Para todo k > 0, a classe de complexidade pk possui o seguinte problema
completo:
pk -SAT = {hi : w1 w2 w3 . . . Qk wk (w1 , . . . , wk ) = 1},
onde e uma formula proposicional arbitraria com kn variaveis, cada wi e uma sequencia
de bits de tamanho n e Qk e um quantificador que depende da paridade de k.
65
Demonstracao. A prova desse resultado pode ser obtida no livro de Papadimitriou [88].
Para os primeiros nveis da hierarquia polinomial, diversos problemas naturais completos sao conhecidos. O artigo de Schaefer e Umans [96] apresenta diversos exemplos.
Em relacao ao caso geral, temos os seguintes resultados.
Lema 4.12. [pk e fechada por reducao polinomial].
Se L pk e L0 p L, entao L0 pk .
Demonstracao. Se L pertence à classe pk , entao existe uma maquina de Turing M que
computa em tempo polinomial e um polinomio q(.) tais que
onde Qk denota ou se k for par ou mpar, respectivamente. Por outro lado, como
L0 p L, existe uma funcao f : {0, 1}? {0, 1}? computavel em tempo polinomial tal
que x L0 se e somente se f (x) L. Portanto,
x L0 f (x) L w1 w2 . . . Qk wk M (f (x), w1 , . . . , wk ) = 1,
Observe que a maquina de Turing Mf (x, w1 , . . . , wk ) = M (f (x), w1 , . . . , wk ) computa em
tempo polinomial, uma vez que f e M sao polinomiais. Isso completa a prova de que
L0 pk .
Lema 4.13. Se existe uma linguagem PH-completa, entao a hierarquia polinomial colapsa
em algum nvel finito, ou seja, existe k 0 tal que PH = pk .
Demonstracao. Se L e uma linguagem PH-completa, entao existe k tal que L pk . Por
hipotese, para toda linguagem L0 PH, temos que L0 p L. Segue pelo lema anterior que
PH pk e portanto PH = pk .
O proximo teorema mostra que, se PH = PSPACE, entao ocorre o colapso da hierarquia polinomial. A demonstracao utiliza o metodo da completude.
Teorema 4.14. Se PH = PSPACE, entao existe k tal que PH = pk .
Demonstracao. A seguinte linguagem e PSPACE-completa:
L = {hM, x, 1s i : M aceita a entrada x utilizando no maximo s celulas de memoria }.
Atraves de simulacao podemos mostrar que L PSPACE. Por outro lado, se L0 e uma
linguagem decidida em espaco polinomial por uma maquina ML0 , podemos usar essa
maquina para provar que L0 p L. Isso mostra que a linguagem L e completa para a
classe PSPACE. Portanto, se PH = PSPACE, temos que a classe de complexidade PH
possui problemas completos. Pelo lema anterior, obtemos que existe k tal que PH = pk ,
como queramos demonstrar.
66
Vimos na secao 2.7 que as classes P e NP podem ser caracterizadas atraves de certos
conceitos logicos. De forma analoga, e possvel caracterizar a classe PH em termos de
expressibilidade logica. A hierarquia polinomial corresponde a` classe de propriedades
expressaveis na logica de segunda ordem. Veja o livro de Immerman [61] para mais
detalhes.
Outras tres definicoes equivalentes para a classe PH sao conhecidas. Uma envolve o
conceito de maquinas alternantes, que sera discutido na proxima secao. As outras duas sao
basedas em oraculos e certos tipos de circuitos, respectivamente. Para mais informacoes,
consulte o livro de Arora e Barak [7], por exemplo.
4.2
Altern
ancia
Nesta secao veremos brevemente como a alternancia de quantificadores utilizada na

definicao da hierarquia polinomial pode ser transferida para dentro das maquinas de Turing. Essas ideias serao u
teis na demonstracao de alguns resultados da secao 4.3. As
maquinas de Turing alternantes foram definidas pela primeira vez no artigo de Chandra
et al. [20].
Uma configuracao de uma maquina de Turing e uma descricao completa do estado da
computacao da maquina. Note que, para determinarmos o proximo passo de uma maquina
de Turing, basta conhecermos o conte
udo atual das fitas, o estado atual da maquina e
a posicao de cada cabeca de leitura. Se M e uma maquina de Turing, dizemos que esse
conjunto de parametros e uma configuracao de M .
A computacao de uma maquina de Turing nao-determinstica M (que sempre termina
sua computacao) com entrada x pode ser vista como uma arvore finita de configuracoes,
de modo que existe uma aresta direcionada ligando as configuracoes C e C 0 se e somente
se C 0 pode ser obtida a partir de C atraves da aplicacao de uma das funcoes de transicao
de M , ou seja, em um passo de computacao. A configuracao inicial descreve o estado de
M antes do primeiro passo de computacao. As folhas da arvore (vertices com grau de
sada zero) representam passos finais da computacao de M , ou seja, configuracoes onde
o estado e de aceitacao ou de rejeicao. Observe que M aceita a entrada x se e somente
se existe um caminho na arvore do vertice que representa a configuracao inicial ate um
vertice que descreve uma configuracao em que M se encontra no estado de aceitacao.
As maquinas de Turing alternantes (MTAs) generalizam naturalmente o conceito de
nao-determinismo em computacao. A u
nica diferenca entre uma MTND e uma MTA e
que a u
ltima possui uma particao no seu conjunto de estados que induz uma nova regra
de aceitacao para a palavra de entrada.
Definic
ao 4.15. [Maquinas de Turing Alternantes]. Uma maquina de Turing alternante
(MTA) e uma maquina de Turing nao-determinstica M onde o conjunto de estados e dado
4.2. Alternancia
67
por Q = Q Q , sendo Q e Q conjuntos disjuntos. Seja x {0, 1}? uma palavra, e

considere a arvore da computacao de M com entrada x, ou seja, a arvore de configurac
oes
discutida anteriormente.
Vamos utilizar essa arvore para definir recursivamente se M aceita a entrada x. Primeiro, todas as folhas da arvore de configuracao com o estado de aceitacao sao definidas
como configuracoes de aceitacao. Uma configuracao C com estado q Q e uma configuracao de aceitacao se e somente se todos os vertices sucessores de C na arvore s
ao
configuracoes de aceitacao. Por outro lado, uma configuracao C com estado q Q e
uma configuracao de aceitacao se e somente se existe na arvore algum vertice sucessor de
C que e uma configuracao de aceitacao. Observe que isso rotula todos os vertices como
configuracoes de aceitacao ou rejeicao. Finalmente, dizemos que M aceita x (ou seja,
M (x) = 1) se a configuracao inicial e uma configuracao de aceitacao.
Uma linguagem L e decidida por uma maquina de Turing alternante M quando x L
se e somente se M (x) = 1. A definicao da complexidade de tempo e de espaco de uma
MTA nao sofre nenhuma alteracao em relacao às mesmas definicoes para MTNDs.
O leitor interessado em exemplos de maquinas de Turing alternantes pode consultar o
livro de Sipser [103].
Definic
ao 4.16. [Alternancia e Classes de Complexidade]. Seja f : N N uma func
ao.
?
Uma linguagem L {0, 1} pertence a classe ATIME(f (n)) se existe uma maquina de
Turing alternante M que decide L em tempo O(f (n)). Similarmente, dizemos que L
pertence a classe ASPACE(f (n)) se existe uma maquina de Turing alternante M que
decide L em espaco O(f (n)).
De modo analogo a`s classes de complexidade P e PSPACE, temos as classes AP e
APSPACE.
Definic
ao 4.17. [Classes Alternantes].
Definimos as seguintes classes de complexidade alternantes:
S
(i) AP = k1 ATIME(nk );
S
(ii) APSPACE = k1 ASPACE(nk );
(iii) AEXP =
k1 ATIME(2
nk
).
A alternancia nos fornece uma nova caracterizacao para diversas classes de complexidade estudadas anteriormente.
Teorema 4.18. [Relacao entre ATIME e ASPACE]. Seja f (n) : N N uma func
ao com
f (n) n para todo natural n. Temos as seguintes inclusoes de classe:
68
(i) ATIME(f (n)) SPACE(f (n)) ATIME(f 2 (n)).

(ii) ASPACE(f (n)) = TIME(2O(f (n)) ).
Demonstracao. A demonstracao desse resultado pode ser encontrada no livro de Sipser
[103].
Corol
ario 4.19.
(i) AP = PSPACE.
(ii) APSPACE = EXP.
(iii) AEXP = EXPSPACE.
O corolario anterior sugere que a introducao de alternancia aumenta significativamente
o poder das classes de complexidade envolvidas (compare o corolario com o teorema 3.11).
Limitando o n
umero de alternancias, podemos obter uma nova caracterizacao dos
diversos nveis da hierarquia polinomial.
Definic
ao 4.20. Seja T (n) : N N uma funcao arbitraria. Para todo inteiro positivo
k, dizemos que uma linguagem L pertence à classe de complexidade pk -TIME(T (n)) se
existe uma maquina de Turing alternante M que decide L em tempo O(T (n)) tal que:
(1) o estado inicial de M pertence ao conjunto Q ; (2) para toda entrada x e para todo
caminho na arvore de configuracoes da computacao de M com entrada x, existe uma
alternancia de tamanho maximo k 1 entre configuracoes com estado em Q e Q .
Teorema 4.21. [Alternancia e PH].
S
Para todo k N, temos pk = c1 pk -TIME(nc ).
Demonstracao. Seja L pk . Entao existe uma maquina de Turing M de tempo polinomial e um polinomio q(.) tal que:
A seguinte maquina pk -alternante decide a linguagem L:
1) Gera nao-deterministicamente com estados existenciais uma palavra w1 {0, 1}q(|x|) .
2) Gera nao-deterministicamente com estados universais uma palavra w2 {0, 1}q(|x|) .
..
.
4.2. Alternancia
69
k) Gera atraves do seu nao-determinismo uma palavra wk {0, 1}q(|x|) . O tipo dos estados
utilizados durante a geracao dessa palavra depende da paridade de k.
Simula deterministicamente com estados do mesmo tipo utilizados na etapa anterior a
computacao de M com entrada hx, w1 , . . . , wk i. Nosso algoritmo aceita x se e somente se
M aceita essa entrada. Observe que, em partes determinsticas da computacao, o tipo de
estado nao altera o conjunto de configuracoes de aceitacao final.
Note que esse algoritmo alternante computa em tempo polinomial. Alem disso, ocorre
exatamente k 1 alternancias entre estados existencias e universais. Finalmente, segue
pela definicao de aceitacao por MTAs que nosso algoritmo decide a linguagem L, ou seja,
L pk -TIME(nc ) para alguma constante c adequada.
Suponha agora que L pk -TIME(nc ) para alguma constante c 1. Em outras
palavras, existe uma MTA A com no maximo k 1 alternancias que decide L em tempo
dnc , para alguma constante d. Vamos exibir uma maquina de Turing determinstica M
que computa em tempo polinomial tal que:
x L w1 w2 w3 . . . Qk wk M (x, w1 , . . . , wk ) = 1 (1),
c
onde |x| = n e wi {0, 1}dn , para 1 i k.

Com entrada hx, w1 , . . . , wk i, M simula deterministicamente a maquina alternante A,
escolhendo a funcao de transicao a ser aplicada atraves das palavras w1 , . . . , wk . Especificamente, M guarda durante a simulacao de A o n
umero k 0 de alternancias ocorridas ate
a simulacao do passo atual. Observe que 0 k 0 k 1. No i-esimo passo a ser simulado
(1 i dnc ), M escolhe a funcao de transicao de acordo com o i-esimo bit da palavra
de entrada wk0 +1 . Por u
ltimo, M aceita hx, w1 , . . . , wk i se e somente se A aceita x com
facil provar por inducao em k que
as escolhas nao-determinsticas obtidas dessa forma. E
M se comporta de modo que (1) seja verdadeiro (em particular, note que bits de entrada
que nao sao acessados por M sao irrelevantes). Isso completa a prova de que L pk .
Observe que a complexidade de tempo determinstica do verificador (calculada em
funcao do tamanho da entrada x) e dada pela complexidade de tempo nao-determinstica
da maquina alternante, e vice-versa. Isso ocorre pois a simulacao pode ser embutida
dentro do codigo das maquinas de Turing envolvidas, o que nao aumenta a complexidade
final dos algoritmos.
Ou
ltimo teorema refina a definicao da hierarquia polinomial, uma vez que cada nvel
de PH se torna a uniao de infinitas classes de complexidade.
70
4.3
Cotas Inferiores para SAT
Por conveniencia, definimos na secao 1.7 a complexidade de espaco de um algoritmo

levando em conta o n
umero de celulas ocupadas pela palavra de entrada. Por isso, todo
algoritmo analisado dessa forma possui complexidade de espaco (n). No entanto, existem
muitos algoritmos interessantes que nao alteram o conte
udo das celulas ocupadas pela
palavra de entrada e utilizam espaco adicional o(n). Utilizar tao pouco espaco e possvel
pois com apenas O(log n) celulas podemos armazenar diversos apontadores e contadores.
Embora os algoritmos sublineares sejam discutidos apenas nesta secao, eles sao bastante
estudados em complexidade computacional.
Especificamene nesta secao, considere a complexidade de espaco de uma maquina de
Turing como sendo o n
umero de celulas distintas acessadas pelas cabecas de leitura de M
em fitas diferentes da fita de entrada. Alem disso, assumimos que as maquinas de Turing
nao podem escrever dados na fita de entrada. Essa fita e usada apenas para a leitura da
palavra de entrada.
Com essa alteracao, podemos discutir a existencia de maquinas de Turing que computam em espaco sublinear. Diversos problemas nao-triviais podem ser resolvidos dessa
forma. Por exemplo, Reingold [92] descobriu recentemente um algoritmo (determinstico) com complexidade de espaco O(log n) que decide se existe um caminho ligando dois
vertices em um grafo nao-direcionado. Notamos tambem que a maioria das reducoes1
utilizadas nas provas de NP-completude podem ser computadas em espaco o(n).
Embora a maioria dos especialistas acredite que SAT
/ P, esse resultado nao parece
proximo de ser provado. Intuitivamente, deve ser muito mais facil demonstrar o seguinte:
1) Nao existe algoritmo de tempo linear que decide SAT.
2) Para todo inteiro positivo b, nao existe algoritmo de espaco O((log n)b ) que decide SAT.
Esses resultados parecem extremamente fracos. No entanto, nao sabemos como provalos. Veremos nesta secao que podemos eliminar pelo menos o mais trivial dos algoritmos.
Especificamente, demonstraremos que nao existe maquina de Turing determinstica que
decide SAT em tempo O(n ) e espaco O((log n)b ), onde > 1 e uma constante e b e um
inteiro positivo arbitrario.
O valor da constante foi melhorado diversas vezes. Atualmente, temos que > 1.8
interessante notar que esses re(Williams [110]). O desafio atual e provar que 2. E
sultados tambem sao validos para maquinas de Turing mais poderosas, dotadas de acesso
aleatorio à memoria. Alem disso, teoremas mais fortes podem ser provados para problemas
1
Consideramos que a palavra computada pela reducao e armazenada em uma fita de sada utilizada
somente para escrita. Assim como ocorre com a fita de entrada, o n
umero de celulas escritas na fita de
sada n
ao e levado em conta no c
alculo da complexidade de espaco do algoritmo.
4.3. Cotas Inferiores para SAT
71
computacionais em nveis superiores da hierarquia polinomial. Por simplicidade, demons

traremos nesta secao que pode ser tomado arbitrariamente proximo de 2 (Lipton e
Viglas [76]).
A tecnica utilizada nessas demonstracoes apareceu pela primeira vez em um artigo
de Kannan [65]. A fim de obtermos uma contradicao, assumimos que uma determinada
inclusao de classes e verdadeira. Utilizamos essa hipotese para mostrar que e possvel
acelerar certos tipos de computacao. Por u
ltimo, mostramos que isso viola algum teorema
de hierarquia conhecido. Isso significa que, em u
ltima instancia, estamos utilizando um
argumento de diagonalizacao, ja que esse metodo e utilizado para provar os teoremas de
hierarquia. O conceito de alternancia sera crucial na hora de colocar em pratica essas
ideias. Observe que o enunciado do nosso resultado nao diz nada sobre alternancia.
Definic
ao 4.22. [Classe de Complexidade DTISP]. Sejam T, S : N N duas func
oes
?
arbitrarias. Dizemos que uma linguagem L {0, 1} pertence à classe DTISP(T (n), S(n))
se existe uma maquina de Turing determinstica M que decide a linguagem L em tempo
O(T (n)) e espaco O(S(n)).
Primeiro mostraremos que NTIME(n) * DTISP(nc , nd ), onde c(c + 2d) < 2. Este
sera o teorema principal desta secao. Em seguida, vamos utilizar a completude
de SAT
2
e tomar d arbitrariamente pequeno para provar que SAT
/ DTISP(n
, (log n)b ), para
todo , b > 0. A demonstracao do resultado principal sera baseada em diversas inclusoes
de classes. Assuma que NTIME(n) DTISP(nc , nd ). Mostraremos que:
NTIME(nk ) DTISP(nkc , nkd ) p2 -TIME(nk(d+c/2) ) NTIME(nck(d+c/2) ),
onde k e um inteiro positivo escolhido de forma que em nenhum momento tenhamos
computacoes em tempo sublinear (precisamos pelo menos ler a palavra de entrada nas
MTs envolvidas na demonstracao). Note que se ck(d + c/2) < k, temos uma violacao do
teorema de hierarquia nao-determinstico demonstrado na secao 3.5. Reescrevendo essa
desigualdade, fica provado que, para c(c + 2d) < 2, NTIME(n) * DTISP(nc , nd ).
Durante as demonstracoes vamos utilizar o fato de que e possvel converter verificadores
de pk em maquinas pk -alternantes e vice-versa sem alterar as complexidades de tempo
envolvidas (veja a prova do teorema 4.21). A primeira inclusao e a mais simples de ser
provada. Utilizamos um argumento usual de preenchimento.
Lema 4.23. Se NTIME(n) DTISP(nc , nd ), entao NTIME(nk ) DTISP(nkc , nkd ),
onde k e qualquer inteiro positivo.
Demonstracao. Primeiro observe que o resultado e bastante intuitivo: se podemos computar n passos nao-determinsticos em tempo (ou espaco) determinstico g(n), entao podemos
computar nk passos nao-determinsticos em tempo (ou espaco) determinstico g(n)k .
72
Suponha que L NTIME(nk ). Considere a linguagem L0 = {hx, 1|x| i : x L}.

Usando uma MTND que decide L em tempo O(nk ), podemos construir outra MTND que
decide L0 em tempo O(n). Da hipotese, temos que L0 DTISP(nc , nd ). Seja M 0 uma
maquina de Turing determinstica que decide L0 com essa complexidade. Considere a
k
k
maquina M que, com entrada x, cria a entrada hx, 1|x| i e retorna M 0 (hx, 1|x| i). Portanto:
k
M (x) = 1 M 0 (hx, 1|x| i) = 1 x L,

k
ou seja, M decide L. Fazendo |x| = n, temos que |hx, 1|x| i| e O(nk ). Como M 0 computa
em tempo O(nc ) e espaco O(nd ), temos que M computa em tempo O(nkc ) e espaco O(nkd ).
Isso completa a demonstracao de que L DTISP(nkc , nkd ).
A proxima inclusao mostra que podemos trocar tempo determinstico por alternancia.
Observe que o resultado nao depende de nenhuma hipotese.
Lema 4.24. DTISP(nkc , nkd ) p2 -TIME(nk(d+c/2) ).
Demonstracao. Utilizaremos pela primeira vez um argumento conhecido como metodo
das configuracoes. Basicamente, vamos determinar se uma palavra e aceita por uma
maquina de Turing verificando se existe um caminho valido entre a configuracao inicial
da maquina e uma configuracao de aceitacao. Alem disso, quebraremos esse problema em
diversas partes, resolvendo cada uma delas separadamente utilizando alternancia.
Seja L DTISP(nkc , nkd ) e considere que M e uma maquina de Turing determinstica
que decide L em tempo O(nkc ) e espaco O(nkd ). Em relacao à computacao de M com uma
entrada x de tamanho n, temos que x L se e somente se existem nkc/2 configuracoes
de M tais que, para todo i N com 1 i < nkc/2 , a configuracao Ci+1 pode ser obtida
a partir da configuracao Ci em k 0 nkc/2 passos (para alguma constante k 0 adequada) e a
configuracao Cnkc/2 e uma configuracao de aceitacao. Portanto,
x L hC1 , . . . , Cnkc/2 i hii [M 0 (x, hC1 , . . . , Cnkc/2 i, hii) = 1],
onde M 0 e uma maquina de Turing determinstica que verifica a condicao anterior. Como
M computa em espaco O(nkd ), temos que |hC1 , . . . , Cnkc/2 i| e O(nkc/2 nkd ). Por isso, apenas
para ler a entrada e obter as configuracoes Ci e Ci+1 , M 0 precisa de O(nk(d+c/2) ) passos. A
computacao de M 0 pode ser feita em tempo O(nkc/2 ). Convertendo M 0 em uma maquina
alternante, obtemos que L p2 -TIME(nk(d+c/2) ).
Finalmente, uma hipotese um pouco mais fraca do que a inicial nos permite trocar
alternancia por tempo nao-determinstico.
Lema 4.25. Se NTIME(nk ) DTIME(nkc ), entao p2 -TIME(nk(d+c/2) ) NTIME(nck(d+c/2) ).
4.3. Cotas Inferiores para SAT
73
Demonstracao. Primeiro observe que esse resultado e razoavel: se podemos computar nk

passos nao-determinsticos em tempo determinstico (nk )c , entao podemos remover um nvel de alternancia com o mesmo acrescimo de complexidade (lembre que p1 -TIME(f (n)) =
NTIME(f (n))).
Formalmente, se L p2 -TIME(nk(d+c/2) ), entao existe uma maquina de Turing determinstica M tal que:
x L w1 w2 [M (x, w1 , w2 ) = 1],
onde M computa em tempo O(nk(d+c/2) ), onde n = |x|. O tamanho das palavras w1 e w2
e limitado pela complexidade de tempo de M .
Como, por hipotese, temos que NTIME(nk ) DTIME(nck ), seque pelo lema 4.23 que
NTIME(nk(d+c/2) ) DTIME(nck(d+c/2) ). Considere a seguinte linguagem:
L0 = {hx, w1 i : w2 tal que M (x, w1 , w2 ) = 0}.
Observe que L0 NTIME(nk(d+c/2) ), e portanto L0 DTIME(nck(d+c/2) ). Como classes determinsticas sao fechadas por complementacao, temos que L0 DTIME(nck(d+c/2) ). Alem
disso, x L se e somente se existe uma palavra w1 tal que hx, w1 i L0 . Portanto, existe
uma maquina de Turing determinstica M 0 com complexidade de tempo O(nck(d+c/2) ) que
satisfaz:
x L se e somente se existe w1 tal que M 0 (x, w1 ) = 1.
Isso prova que L NTIME(nck(d+c/2) ).
Teorema 4.26. NTIME(n) * DTISP(nc , nd ), onde c(c + 2d) < 2.
Demonstracao. A demonstracao e imediata a partir dos lemas 4.23, 4.24 e 4.25 e da
discussao apresentada apos a definicao 4.22.
Corol
ario 4.27. [Limitante Inferior para SAT].
Para todo inteiro positivo b e para todo > 0, SAT

/ DTISP(n 2 , (log n)b ).
possvel provar que o problema de decidir pertinencia para linguagens
Demonstracao. E
em NTIME(t(n)) pode ser reduzido ao problema de verificar se uma formula proposicional
de tamanho O(t(n) log t(n)) e satisfatvel. Alem disso, cada bit de sada dessa reducao
pode ser computado em tempo linear e espaco poli-logaritmo
(veja Arora e Barak [7]).
2
Suponha que existam e b tais que SAT DTISP(n
, (log n)b ). Sabemos
que, para
b
todo > 0, uma funcao O((log n) ) e tambem O(n ), e portanto SAT DTISP(n 2 , n ).
Alem disso, se L NTIME(n), entao x L se e somente se a formula proposicional de tamanho n log n associada a x e satisfatvel (veja a discussao do paragrafo anterior). Como essareducao pode ser computada em tempo linear e espaco poli-logaritmo e
SAT DTISP(n 2 , n ), existe um polinomio p(.) tal que:
74
+ n, (n log n) + p(log n)) DTISP(n 2/2 , n2 ).
Podemos tomar arbitrariamente pequeno de modo que, para c = 2 /2 e d = 2,

tenhamos c(c + 2d) < 2. No
entanto, isso contradiz o teorema 4.26. Por esse motivo,
2
temos que SAT
/ DTISP(n
, (log n)b ), como queramos demonstrar.
NTIME(n) DTISP((n log n)
Recentemente, Williams [111] formalizou todas as provas conhecidas desses limitantes

inferiores. Atraves disso, foi possvel desenvolver um programa de computador capaz de
melhorar o valor da constante obtido atraves desses metodos. Infelizmente, seu trabalho
sugere que essas tecnicas nao sao capazes de provar que 2.
4.4
Reduc
oes e NP coNP
Na secao 2.5 discutimos a nocao de reducao entre problemas computacionais e introduzimos o conceito de reducao de Karp. Essa nocao restrita de reducao foi estudada
porque ela e suficiente para a teoria de NP-completude. No entanto, em complexidade
computacional e mais interessante desenvolver uma nocao de reducao que se comporte
da seguinte maneira: um problema A se reduz a um problema B se a existencia de um
algoritmo eficiente para B implica a existencia de um algoritmo eficiente para A. Por
exemplo, pode ser interessante chamar diversas vezes o algoritmo eficiente que resolve o
problema B quando se quer resolver o problema A. Alem disso, podemos ter diferentes
caminhos de execucao de acordo com as respostas obtidas por essas chamadas. Essa nocao
mais geral de reducao entre problemas e capturada pela nocao de reducao de Cook.
Esse conceito pode ser facilmente formalizado atraves do uso de maquinas de Turing
com oraculo (MTO). As MTOs sao maquinas de Turing usuais que possuem a habilidade
adicional de realizar chamadas a um oraculo L. Mais especificamente, L {0, 1}? e
uma linguagem arbitraria e a maquina de Turing com acesso ao oraculo L e capaz de
verificar instantaneamente se uma dada palavra pertence a` linguagem L. Para isso, basta
a MTO escrever essa palavra em uma fita adicional chamada fita do oraculo e utilizar uma
instrucao especial que obtem a resposta do oraculo. Esse procedimento pode ser realizado
diversas vezes durante a computacao da MTO.
Definic
ao 4.28. [Maquinas de Turing com Oraculo (MTOs)]. Uma maquina de Turing
M com oraculo e uma maquina de Turing com uma fita especial adicional, chamada fita
de oraculo, e tres estados especiais: qoraculo , qsim e qnao . A computacao de M e sempre
relativa a um oraculo L {0, 1}? . Quando M entra no estado qoraculo , seu proximo estado
de execucao depende do conte
udo w escrito na fita de oraculo. O novo estado sera qsim
caso w L, e qnao se w
/ L. O conteu
do da fita de oraculo permanece inalterado apos
essa chamada. Alem disso, independente da linguagem L utilizada como oraculo, cada
4.4. Reducoes e NP coNP
75
resposta obtida atraves do oraculo conta como apenas um passo computacional. Se M e

uma maquina de Turing com oraculo, L {0, 1}? e uma linguagem e x {0, 1}? e uma
palavra de entrada, entao o resultado da computacao de M com entrada x e com acesso
ao oraculo L sera denotado por M L (x). As maquinas de Turing nao-determinsticas com
oraculo sao definidas similarmente.
Definic
ao 4.29. [Classes de Complexidade com Oraculo]. Para toda linguagem L
?
{0, 1} , definimos a classe de complexidade PL como sendo o conjunto de linguagens que
podem ser decididas em tempo polinomial por maquinas de Turing determinsticas com
acesso ao oraculo L. Similarmente, NPL denota o conjunto de linguagens que podem ser
decididas em tempo polinomial por maquinas de Turing nao-determinsticas com acesso
ao oraculo L.
Definic
ao 4.30. [Reducao de Cook]. Dizemos que uma linguagem L e Cook-redutvel a
0
uma linguagem L0 (denotado por L T L0 ) se L PL .
Observe que a reducao de Cook captura o conceito intuitivo de reducao discutido no
incio da secao. Alem disso, observe que se L0 P e L T L0 , entao L P. Isso e
valido pois podemos substituir as chamadas ao oraculo L0 pela propria computacao de
uma maquina eficiente que decide L0 . Como a composicao de polinomios e novamente um
polinomio, obtemos a partir disso um algoritmo eficiente para L. Por u
ltimo, se L p L0 ,
entao L T L0 (a reducao de Karp e um caso particular da reducao de Cook).
Veremos agora como a reducao de Karp e a reducao de Cook se relacionam com a
classe NP coNP.
Teorema 4.31. Seja L {0, 1}? uma linguagem e suponha que L NP coNP. Se L
e NP-completa, entao NP = coNP.
Demonstracao. Primeiro vamos provar que a classe coNP e fechada por reducao de Karp.
Seja L0 coNP e suponha que L00 p L0 . Entao L00 p L0 . Como L0 NP e NP e uma
classe fechada por reducao de Karp (a composicao de uma reducao eficiente com uma
MTND eficiente e novamente um MTND eficiente), temos que L00 NP. Isso prova que
L00 coNP.
Considere agora a linguagem L do enunciado do teorema. Como L coNP, L e NPcompleta e coNP e fechada por reducao de Karp, temos que NP coNP. Por outro lado,
se L0 coNP entao L0 NP. Como NP coNP, segue que L0 coNP. Por definicao, isso
significa que L0 NP, ou seja, coNP NP. Isso completa a prova de que NP = coNP.
Portanto, para provar que NP = coNP basta demonstrar a existencia de um problema
NP-completo em coNP. No entanto, o que ocorre se esse problema for completo em relacao
a` reducao de Cook? Com um pouco mais de trabalho, e possvel obter o mesmo resultado.
O proximo teorema e devido à Selman [100].
76
Teorema 4.32. Seja L uma linguagem em NP coNP. Se toda linguagem em NP for

Cook-redutvel à linguagem L, entao NP = coNP.
Demonstracao. Seja L NP coNP. Observe que, pelo mesmo argumento utilizado na
prova do teorema 4.31, basta provar que se L0 T L entao L0 coNP. Por sua vez, para
provar isso e suficiente demontrar que se L0 T L entao L0 NP, ja que L0 T L se e
somente se L0 T L.
Como L NP coNP, existem verificadores eficientes V1 e V2 tais que:
(1) z L se e somente se w {0, 1}p1 (|x|) tal que V1 (z, w) = 1;
(2) z
/ L se e somente se w {0, 1}p2 (|x|) tal que V2 (z, w) = 1.
Ou seja, podemos provar eficientemente que uma palavra arbitraria z {0, 1}? pertence
ou nao a` linguagem L.
Para demonstrarmos que a linguagem L0 NP precisamos exibir um verificador eficiente V 0 para L0 . Seja M a maquina de Turing com oraculo que computa a reducao
L0 T L. Portanto, temos que z L0 se e somente se M L (z) = 1.
Observe que podemos verificar eficientemente cada resposta emitida pelo oraculo L
usando os verificadores V1 e V2 . Por isso, definimos V 0 de forma que, dada uma palavra
w = ((z1 , r1 , w1 ), . . . , (zk , rk , wk )), temos V 0 (x, w) = 1 se e somente se:
(a) M aceita a entrada x invocando o oraculo com as palavras z1 , . . . , zk na fita de oraculo
durante sua computacao;
(b) As respostas obtidas por M nas chamadas ao oraculo sao dadas pelos bits r1 , . . . , rk .
No entanto, como V 0 e uma maquina determinstica que nao possui acesso ao oraculo
L, usamos as palavras w1 , . . . , wk para confirmar a consistencia das respostas codificadas
pelos bits ri . Isso significa que V 0 verifica se V1 (zi , wi ) = 1 quando ri = 1, e se V2 (zi , wi ) =
1 quando ri = 0.
imediato a partir da construcao de V 0 que se x L0 entao existe palavra w tal que
E
V 0 (x, w) = 1. Por outro lado, se V 0 (x, w) = 1 para alguma palavra w, entao essa palavra
codifica de forma consistente a computacao de M e as respostas dadas pelo oraculo L, ou
seja, M L (x) = 1 e portanto x L0 .
Finalmente, observe que como M computa em tempo polinomial e os certificados
aceitos por V1 e V2 sao polinomialmente limitados, temos que os certificados aceitos por
V 0 sao formados pela concatenacao de uma quantidade polinomial de palavras de tamanho
polinomial, ou seja, os certificados de V 0 sao polinomialmente limitados. Alem disso, V 0
computa em tempo polinomial pois as maquinas M , V1 e V2 sao maquinas eficientes. Isso
completa a prova de que V 0 e um verificador eficiente para L0 , ou seja, L0 NP.
4.5. O Teorema de Ladner
77
As maquinas de Turing com oraculo serao utilizadas novamente no captulo 5.
4.5
O Teorema de Ladner
Dada uma linguagem L em NP, se L

/ P entao L e NP-completa? Embora seja possvel
demonstrar que milhares de problemas sao NP-completos, esse resultado nao e valido. De
fato, a menos que P = NP, e possvel provar que existem linguagens intermediarias entre
a classe P e a classe de linguagens NP-completas (NPC). Esse resultado e conhecido como
Teorema de Ladner [73].
O problema computacional exibido por Ladner em sua demonstracao e bastante artificial. No entanto, e bem provavel que alguns problemas naturais possuam dificuldade
intermediaria entre as duas classes. Por exemplo, muitos pesquisadores acreditam que
certos problemas ligados a` criptografia (em particular, fatoracao e logaritmo discreto) nao
pertencam a`s classes P e NPC, embora sejam membros da classe NP.
Alem disso, ha fortes razoes para acreditarmos que algumas linguagens aparentemente
difceis de NP nao sao NP-completas. Por exemplo, algumas dessas linguagens estao em
NP coNP. Se algum desses problemas for NP-completo, segue pelo Teorema 4.31 que
NP = coNP, um resultado considerado improvavel pela maior parte dos pesquisadores
em complexidade computacional. Outro caso interessante ocorre com o problema de
verificar se dois grafos arbitrarios sao isomorfos (ISO-GRAFOS). Se esse problema for
NP-completo, entao ocorre o colapso da hierarquia polinomial.
Teorema 4.33. Se ISO-GRAFOS e uma linguagem NP-completa, entao p2 = p2 .
Demonstracao. A prova desse resultado pode ser encontrada no artigo original de Boppana
et al. [14].
No entanto, tais resultados tambem servem como um indcio de que esses problemas
podem admitir algoritmos eficientes. Por exemplo, existe um algoritmo linear que verifica
se dois grafos planares sao isomorfos (veja o artigo de Hopcroft e Wong [59]). Um resultado
muito mais geral aparece em um artigo recente de Grohe [49], que demonstra a existencia
de algoritmos eficientes capazes de verificar o isomorfismo em diversas classes interessantes
de grafos.
Existem duas demontracoes conhecidas do teorema de Ladner. A primeira envolve
um argumento de diagonalizacao atrasada (veja a prova do teorema 3.34) e aparece no
artigo original de Ladner. Ela tambem pode ser obtida nos livros de Goldreich [47] e
Papadimitriou [88]. Uma segunda prova foi descoberta por Impagliazzo e pode ser obtida
no livro de Arora e Barak [7]. Por utilizar uma tecnica diferente, vamos apresentar esta
u
ltima demonstracao. Um esboco das duas provas esta descrito em um manuscrito de
Fortnow [37].
78
Teorema 4.34. [Teorema de Ladner]. Suponha que P 6= NP. Entao existe uma linguagem
L {0, 1}? tal que:
(i) L NP;
(ii) L
/ P;
(iii) L nao e uma linguagem NP-completa.
Demonstracao. Seja f : N N uma funcao arbitraria. Considere a seguinte linguagem:
f (n)
SATf = {01n
: || = n e SAT }.
Vamos definir uma funcao H(n) : N N de forma que a linguagem SATH satisfaca os
requisitos do teorema. Primeiro, observe que mais uma vez estamos utilizando o metodo
do preenchimento, pois a complexidade de SATH depende essencialmente do crescimento
da funcao H (assumindo que essa funcao pode ser computada de forma eficiente). Por
outro lado, definiremos H de forma que seu crescimento dependa da dificuldade do proprio
problema SATH (H sera uma funcao bem-definida, uma vez que o valor H(n) depende
apenas de valores H(n0 ) para n0 < n):
Considere uma enumeracao das maquinas de Turing. Para todo n
umero natural n, definimos H(n) como sendo o menor inteiro i < log log n tal que, para
toda palavra x {0, 1}? com |x| log n, a maquina de Turing Mi computa,
tendo x como entrada, em no maximo i|x|i passos e Mi (x) = 1 se e somente
se x SATH . Se nao existe tal i, entao definimos H(n) = log log n.
A funcao H foi definida dessa forma para que possamos provar o seguinte resultado.
Lema 4.35. SATH P se e somente se H(n) e O(1) (ou seja, existe uma constante C
tal que H(n) C para todo inteiro n).
Demonstracao. Primeiro, suponha que SATH P. Seja M uma maquina de Turing que
decide essa linguagem em no maximo c1 nc1 passos. Como adotamos uma codificacao de
maquinas de Turing em que cada maquina e representada por infinitas palavras, existe
i
um inteiro i c1 tal que M e equivalente a Mi . Se n > 22 , entao i < log log n e da segue
da definicao de H(n) que temos H(n) i. Isso prova que H(n) e uma funcao O(1).
Suponha agora que H(n) seja O(1). Como H so pode assumir um n
umero finito de
valores, existe um inteiro i tal que H(n) = i para valores arbitrariamente grandes de n.
Segue pela definicao da funcao H(n) que a maquina de Turing Mi decide SATH em tempo
ini . Isso prova que SATH P.
Vamos agora demonstrar que H(n) pode ser computada eficientemente.
4.5. O Teorema de Ladner
79
Lema 4.36. A funcao H(n) pode ser computada em tempo O(n5 ).

Demonstracao. Para computar H(n) basta: (1) computar H(i) para todo i log n;
(2) decidir SAT em instancias de tamanho limitado por log n; (3) simular no maximo
log log n maquinas de Turing com entradas de tamanho limitado por log n por no maximo
log log n(log n)log log n passos. Para n suficientemente grande, temos:
log log n(log n)log log n = log log n(2log log n )log log n log log n (2log n ) n2 .
Por isso, podemos computar a funcao H(n) em complexidade de tempo T (n), onde a
funcao T (n) satisfaz:
T (n) log n T (log n) + O(n2 ) + O((log log n)nn2 ).
O termo log n T (log n) limita o n
umero de passos realizados em (1). Alem disso, em O(n2 )
passos podemos computar as instancias de SAT (2). Finalmente, o u
ltimo termo limita
o tempo gasto com as simulacoes nas diversas entradas (3). Por conveniencia, podemos
escrever:
T (n) log n T (log n) + O(n4 ).
facil provar por inducao que, para valores suficientemente grandes de n, temos T (n)
E
kn5 , onde k e uma constante adequada. Isso completa a demonstracao de que H(n) pode
ser computada em tempo O(n5 ).
O teorema de Ladner segue a partir dos proximos lemas.
Lema 4.37. SATH NP.
Demonstracao. Os certificados para a linguagem SATH sao os mesmos utilizados na demonstracao de que SAT e uma linguagem NP-completa: as sequencias de bits que satisfazem a formula codificada na palavra de entrada x. A seguir descrevemos o verificador V
para a linguagem SATH . Com entrada hx, wi, V verifica primeiro se x = 01k para algum
inteiro k, e rejeita a entrada caso contrario. Seja || = n. O verificador V computa H(n)
e compara se k = nH(n) , rejeitando a palavra de entrada se isso nao ocorre. Finalmente,
V aceita a entrada hx, wi se e somente se (w) = 1.
Pelo lema 4.36, a funcao H(n) pode ser computada em tempo polinomial em n. No
nosso caso, n e dado pelo tamanho da formula , e portanto e limitado pelo tamanho da
entrada. Isso prova que V computa em tempo polinomial e portanto SATH NP.
Lema 4.38. SATH
/ P.
80
Demonstracao. Suponha que SATH P. Pelo lema 4.35, H(n) C para alguma constante
C, ou seja, as palavras de SATH sao apenas as palavras de SAT preenchidas com uma
quantidade polinomial de bits adicionais. Por isso, segue facilmente que SAT p SATH , o
que prova que SAT P e portanto P = NP. Como isso contradiz a hipotese do teorema,
temos que SATH
/ P.
Lema 4.39. SATH nao e uma linguagem NP-completa.
Demonstracao. Suponha que SATH seja uma linguagem NP-completa. Entao, existe uma
funcao g(x) : {0, 1}? {0, 1}? que computa a reducao SAT p SATH em tempo O(nk1 ),
para algum inteiro k positivo. Isso garante que existe um inteiro n0 tal que, para entradas
de tamanho maior ou igual a n0 , a reducao anterior pode ser computada em tempo nk .
Como provamos no lema 4.38 que SATH
/ P, segue pelo lema 4.35 que a funcao H(n)
assume valores arbitrariamente grandes. Seja n1 o menor inteiro maior ou igual a n0 tal
que, para todo n n1 , temos H(n) > k. Vamos mostrar que podemos construir um
algoritmo recursivo A que decide a linguagem SAT em tempo polinomial. Com entrada
de tamanho n, A computa da seguinte maneira:
(1) Se n < n1 , entao A decide se a formula e satisfatvel atraves de uma busca exaustiva.
(2) Caso contrario, A computa w = g(). Se a palavra w obtida nao for da forma
H(||)
01||
, entao A rejeita a formula . Caso contrario, recursivamente, A retorna A().
Seja || = n0 . Observe que se n0 < n1 , entao nao ocorrem mais chamadas recursivas
apos a chamada realizada no passo 2. Se n0 n1 , o tamanho de w e limitado pela
complexidade de tempo da reducao computada por g(), ou seja, |w| nk . Lembre que
0
temos || = n e que |w| = || + 1 + ||H(||) = n0 + 1 + n0H(n ) . Portanto, temos:
0
n0k+1 n0 + 1 + n0k+1 n0 + 1 + n0H(n ) = |w| nk .

Como k e fixo, para valores suficientemente grandes de n temos que n0 n/2, ou seja,
|| ||/2. Isso mostra que o algoritmo A pode ser modificado de forma a realizar no
maximo log n chamadas recursivas (adequamos o valor de n1 na definicao de A). Como as
funcoes g() e H(n) podem ser computadas em tempo polinomial, segue que a complexidade de tempo do algoritmo resultante e polinomial. Isso prova que SAT P, e portanto
P = NP. Como isso contradiz a hipotese do teorema, fica demonstrado que SATH nao e
uma linguagem NP-completa.
Isso completa a prova do Teorema de Ladner.
4.6. NP-Completude, Isomorfismo e Densidade
81
possvel provar um resultado ainda mais forte. Se P 6= NP, entao existem infinitos
E
nveis de dificuldade entre as classes P e NP.
Teorema 4.40. Suponha que P 6= NP. Entao existe uma sequencia infinita de linguagens
L1 , L2 , . . . em NP \ P, de forma que Li+1 e Karp-redutvel à Li , mas Li nao e Cookredutvel à Li+1 .
Demonstracao. Veja a prova desse resultado no livro de Goldreich [47].
Do ponto de vista matematico, entender a complexidade computacional dos problemas
intermediarios e uma tarefa extremamente difcil. Se P 6= NP, sabemos que nenhum
problema NP-completo possui algoritmo eficiente. No entando, continuamos sem saber,
por exemplo, se o problema do isomorfismo entre grafos pode ser resolvido de forma
eficiente.
4.6
NP-Completude, Isomorfismo e Densidade
Durante a computacao de uma maquina de Turing ocorre apenas a manipulacao de

smbolos, atraves de regras bem definidas. Por isso, do ponto de vista da maquina,
nao existem grafos, matrizes ou mesmo n
umeros inteiros. Essas sao interpretacoes que
atribumos aos smbolos manipulados.
Lembre que a demonstracao de que SAT e um problema completo prova essencialmente
que suas instancias sao capazes de codificar computacao. Alem disso, vimos na secao 2.5
que se L e uma linguagem em NP, entao SAT p L se e somente se L e uma linguagem
NP-completa. Em outras palavras, nao existe linguagem NP-completa que nao seja capaz
de codificar computacao.
Portanto, faz sentido investigar mais a fundo se existe realmente alguma diferenca
estrutural entre os problemas NP-completos. A menos de uma mudanca facilmente computavel na codificacao das instancias, nao seriam todos eles o mesmo problema?
Definic
ao 4.41. [Isomorfismo Polinomial entre Linguagens]. Dizemos que as linguagens
L1 , L2 {0, 1}? sao polinomialmente isomorfas (denotado por L1 p L2 ) se existe uma
funcao f : {0, 1}? {0, 1}? tal que:
(i) f e uma bijecao, ou seja, f e uma funcao injetora e sobrejetora;
(ii) Para todo x {0, 1}? , temos x L1 se e somente se f (x) L2 ;
(iii) As funcoes f e f 1 podem ser computadas em tempo polinomial.
Nesse caso, dizemos que f e f 1 sao isomorfismos polinomiais.
82
O leitor interessado pode observar na literatura que as reducoes usuais utilizadas para
provar a completude dos problemas quase nunca sao isomorfismos polinomiais. Geralmente, isso ocorre porque as instancias produzidas na reducao sao muito especficas, ao
passo que o isomorfismo polinomial precisa ser sobrejetivo.
No entanto, existe um metodo relativamente simples que pode ser usado para converter diversas reducoes em isomorfismos polinomiais. Em particular, e possvel aplicar esse
metodo para demonstrar que todos os problemas NP-completos conhecidos sao polinomialmente isomorfos. Consulte o livro de Papadimitriou [88] para mais detalhes. Devido
a essa enorme evidencia experimental, Hartmanis e Berman [50] sugeriram a seguinte
conjectura.
Quest
ao em Aberto 4.42. [Conjectura do Isomorfismo de Berman-Hartmanis]. Se
L1 , L2 {0, 1}? sao linguagens NP-completas, entao L1 e L2 sao polinomialmente isomorfas?
Como o isomorfismo polinomial e uma relacao de equivalencia, essa conjectura procura
estabelecer essencialmente que todos os problems NP-completos sao equivalentes.
simples perceber que a conjectura do isomorfismo implica que P 6= NP. Primeiro,
E
suponha que P = NP. Entao todas as linguagens nao-triviais de NP sao NP-completas, e
portanto polinomialmente isomorfas. Por outro lado, uma linguagem finita e uma linguagem infinita nao podem ser polinomialmente isomorfas, uma vez que nao existe bijecao
entre um conjunto finito e um conjunto infinito.
Apesar da conjectura do isomorfismo ser bastante intuitiva, alguns resultados indicam
que ela pode ser falsa. Em particular, ela nao e valida na presenca de um oraculo aleatorio
(Kurtz et al. [71]). Veremos como resultados envolvendo oraculos aleatorios podem ser
formalizados na secao 5.5.
A proxima definicao introduz uma propriedade estrutural importante das linguagens.
Definic
ao 4.43. [Densidade de uma Linguagem]. Seja L {0, 1}? uma linguagem arbitraria. A funcao de densidade de L e dada por densL (n) = |{x L : |x| n}|. Ou
seja, densL (n) e o n
umero de palavras de tamanho menor ou igual a n que pertecem à
linguagem L.
Observe que o crescimento da funcao de densidade e no maximo exponencial. Por isso,
podemos particionar as linguagens em duas classes.
Definic
ao 4.44. [Linguages Densas e Linguagens Esparsas]. Seja L {0, 1}? uma linguagem arbitraria e densL (n) : N N sua funcao de densidade. Dizemos que L e uma
linguagem esparsa se existe um polinomio p(x) com densL (n) p(n), para todo inteiro
positivo n. Caso contrario, dizemos que L e uma linguagem densa.
83
A seguir vamos relacionar a nocao de densidade com o conceito de isomorfismo polinomial.

Teorema 4.45. [Isomorfismo Polinomial e Densidade]. Sejam L1 , L2 {0, 1}? duas
linguagens arbitrarias e assuma que L1 e L2 sao polinomialmente isomorfas. Ent
ao L1 e
uma linguagem densa se e somente se L2 e uma linguagem densa.
Demonstracao. Como L1 p L2 se e somente se L2 p L1 , basta provar que se L1 e
uma linguagem esparsa entao L2 e uma linguagem esparsa. Sejam f : {0, 1}? {0, 1}?
um isomorfismo polinomial entre as linguagens L1 e L2 e p(.) um polinomio tal que
densL1 (n) p(n). Como f 1 (x) pode ser computada em tempo polinomial, existe um
polinomio q(.) tal que, para toda palavra x com |x| n, temos |f 1 (x)| q(n). Como f 1
e uma funcao injetora e x L2 implica que f 1 (x) L1 , segue que densL2 (n) p(q(n)).
Isso completa a prova de que L2 e uma linguagem esparsa.
Nao e difcil provar que algumas linguagens NP-completas envolvendo grafos sao densas. Por isso, se a conjectura do isomorfismo e verdadeira, nao existem linguagens NPcompletas esparsas. No entanto, nao e necessario assumir essa conjectura para provar
esse resultado. Mahaney [78] foi o primeiro a demonstrar que, a menos que P = NP, nao
existem linguagens NP-completas esparsas. Apresentaremos a seguir uma prova muito
mais simples descoberta posteriormente por Ogihara e Watanabe [86].
Teorema 4.46. [Teorema de Mahaney]. Se P 6= NP, entao toda linguagem NP-difcil e
densa.
Demonstracao. Suponha que S {0, 1}? seja um linguagem esparsa, ou seja, existe um
polinomio p(.) tal que densS (n) p(n) para todo inteiro positivo n. Vamos demonstrar
que se SAT p S (i.e., S e uma linguagem NP-difcil), entao existe um algoritmo polinomial para SAT. Observe que, pela contrapositiva, isso demonstra o teorema de Mahaney.
A prova utiliza uma variacao do metodo do prefixo, encontrado pela primeira vez na
demonstracao do teorema 2.15.
Seja (x1 , . . . , xn ) uma formula proposicional em forma normal conjuntiva. Toda
palavra com no maximo n bits pode ser considerada uma atribuicao parcial para a formula
. Se = 1 . . . k e = 1 . . . k sao palavras de k bits, dizemos que se nao
precede segundo a ordem lexicografica. Se e uma formula satisfatvel, dizemos que
a atribuicao e a menor atribuicao que satisfaz se () = 1 e, para toda atribuicao
com ( ) = 1, temos . Alem disso, dizemos que uma atribuicao parcial pode
ser estendida a uma atribuicao que satisfaz a formula se existe 0 {0, 1}n|| tal que
(0 ) = 1. Considere a seguinte linguagem:
SAT* = {h(x1 , . . . , xn ), i : , 0 {0, 1}n|| tal que (0 ) = 1}.
84
A linguagem SAT* e formada por pares de formulas e atribuicoes parciais tais que
existe uma atribuicao parcial menor ou igual (segundo a ordem lexicografica) a` atribuicao
parcial de entrada, e que pode ser estendida a uma atribuicao que satisfaz a formula de
entrada. Observe que 0 serve como certificado eficiente para a linguagem SAT*. Por
isso, SAT* NP. Como SAT e uma linguagem NP-completa, temos que SAT* p SAT.
Pela transitivade da reducao de Karp, obtemos que SAT* p S. Seja h : {0, 1}? {0, 1}?
uma reducao de tempo polinomial entre SAT* e S. Como para toda atribuicao parcial
temos || ||, existe uma constante c1 tal que |h(h, i)| c1 ||c1 . Observe que essa
constante e independente da atribuicao parcial . Por isso, segue a partir da definicao
do polinomio p(.) que existem no maximo p(c1 ||c1 ) palavras em S que sao imagem de
h(h, .i). Seja N esse n
umero.
Exibiremos um algoritmo polinomial que encontra a menor atribuicao que satisfaz a
formula de entrada (x1 , . . . , xn ), caso ela seja satisfatvel. Associamos a essa formula
uma arvore binaria de atribuicoes parciais de altura n + 1 (no nvel inicial temos a palavra
vazia , no proximo nvel as palavras 0 e 1, e assim por diante). Vamos explorar essa
arvore e encontrar a menor atribuicao que satisfaz (caso ela exista). No entanto, nosso
algoritmo verificara (em tempo polinomial) no maximo N nos em cada nvel da arvore.
Como esse valor e polinomial no tamanho da entrada, teremos um algoritmo eficiente
que podera ser usado para decidir a linguagem SAT. Desenvolveremos e provaremos a
corretude do nosso algoritmo por inducao:
No i-esimo nvel da arvore, temos no maximo N nos (atribuicoes de tamanho
i) a serem analisados. Alem do mais, se a formula for satistatvel, algum
desses nos pode ser estendido à menor atribuicao que satisfaz .
No caso i = 0, a hipotese de inducao e claramente satisfeita, uma vez que se e
satisfatvel, entao a palavra vazia pode ser estendida a` menor atribuicao que satisfaz .
Suponha que o algoritmo tenha executado ate o i-esimo nvel da arvore e que a hipotese
de inducao seja verdadeira nesse nvel. Seja k N o n
umero de nos restantes ao fim dessa
etapa. Inicialmente, geramos todos as 2k atribuicoes parciais a serem verificadas no nvel
i + 1. Segue a partir da hipotese de inducao e por exaustao que alguma delas pode
ser estendida a` menor atribuicao que satisfaz a formula , caso seja satisfatvel. Se
2k N , entao a hipotese de inducao continua verdadeira e partimos para o nvel seguinte
da arvore. Caso contrario, sejam 1 , . . . , 2k as atribuicoes parciais obtidas nessa etapa.
Em primeiro lugar, computamos em tempo polinomial as palavras wj = h(h, j i),
para 1 j 2k. Se existirem ndices j e j 0 tais que wj = wj 0 , entao h, j i SAT* se
e somente se h, j 0 i SAT* (lembre que h e uma reducao entre SAT* e S). Afirmamos
que a maior dessas atribuicoes parciais nao pode ser estendida à menor atribuicao que
satisfaz . A fim de obtermos uma contradicao, suponha que isso seja possvel. Assuma,
85
sem perda de generalidade, que j j 0 . Vamos considerar os dois cenarios possveis. Por
um lado, se h, j 0 i SAT*, vimos anteriormente que h, j i SAT*. Como j j 0 e
h, j i SAT*, j 0 nao pode ser estendida a` menor atribuicao que satisfaz (note que
j 6= j 0 ). Por outro lado, se h, j 0 i
/ SAT*, entao j 0 nao pode ser estendida a` nenhuma
atribuicao que satisfaz , e muito menos a` menor delas. Por isso, precisamos continuar
a execucao do algoritmo guardando apenas as atribuicoes parciais que possuem imagens
distintas segundo a funcao h, dando preferencia por aquelas que sao menores segundo à
ordem lexicografica.
Seja k 0 o n
umero de atribuicoes parciais (com imagens distintas por h) restantes. Se
0
k N , passamos para o proximo nvel da arvore. Caso contrario, eliminamos as k 0 N
primeiras atribuicoes parciais segundo a ordem lexicografica e passamos para a proxima
etapa. Isso pode ser feito pois, caso alguma das k 0 N primeiras atribuicoes parciais
possa ser estendida à uma atribuicao que satisfaz , teremos mais do que N atribuicoes
parciais restantes formando palavras da forma h, .i pertencentes à SAT*, e portanto mais
do que N imagens distintas h(h, .i) em S, o que contradiz a definicao de N . Portanto, o
i + 1-esimo passo e completado e a hipotese de inducao continua valida.
Finalmente, utilizamos o algoritmo anterior para encontrar em tempo polinomial
um conjunto de no maximo N atribuicoes de tamanho n para a formula de entrada
(x1 , . . . , xn ). Alem disso, por hipotese, alguma dessas atribuicoes e a menor atribuicao
possvel que satisfaz a formula , caso seja satisfatvel. Verificamos o valor de (j )
para cada atribuicao j e descobrimos se a formula de entrada e satisfatvel. Isso completa
a descricao do algoritmo de tempo polinomial que decide SAT.
Um importante precursor desse teorema foi um resultado provado por Berman [11].
Corol
ario 4.47. [Teorema de Berman]. Suponha que alguma linguagem unaria L {1}?
seja NP-completa. Entao P = NP.
Demonstracao. Note que toda linguagem unaria e esparsa. O resultado segue pelo teorema
de Mahaney.
possvel demonstrar que a dificuldade das linguagens de baixa densidade em NP
E
depende da relacao entre certas classes de complexidade mais fortes.
Teorema 4.48. EXP 6= NEXP se e somente se existe uma linguagem esparsa em NP \ P.
Demonstracao. A prova desse resultado pode ser obtida no artigo original de Hartmanis
et al. [53].
Observe que esse teorema fornece uma prova alternativa do teorema de Ladner atraves
da hipotese mais forte de que EXP 6= NEXP, uma vez que uma linguagem esparsa nao
pode ser NP-completa pelo teorema de Mahaney.
86
4.7
Algoritmos Otimos
para NP
Nesta secao vamos provar que todo problema de busca com solucoes eficientemente
verificaveis admite um algoritmo (assintoticamente) otimo. Alem disso, vamos exibir
explicitamente o seu codigo. Embora seja possvel provar a otimalidade do algoritmo, a
demonstracao apresentada nao deixa nenhuma pista sobre sua complexidade.
Seja V um verificador eficiente para uma linguagem L NP. Na secao 2.3 definimos o
problema de busca relacionado ao verificador V : dada uma palavra de entrada x, encontrar
uma palavra w tal que V (x, w) = 1, ou indicar que tal w nao existe.
Definic
ao 4.49. Sejam V um verificador eficiente para uma linguagem L NP e q(x) o
polinomio que descreve o tamanho dos certificados aceitos por V . Denotamos por SV (x) =
{w {0, 1}q(|x|) : V (x, w) = 1} o conjunto de solucoes da entrada x em relacao ao
verificador V .
Para simplificar a demonstracao e o enunciado do resultado, nao vamos considerar o
modelo computacional de maquinas de Turing nesta secao. Assuma que todos os algoritmos discutidos podem ser implementados em um modelo computacional capaz de simular
t passos de sua computacao em no maximo kt passos, onde k e uma constante adequada.
Essa simplificacao nao oferece qualquer risco, uma vez que o teorema desta secao nao sera
utilizado no resto do texto. Se A e um algoritmo, entao tA (x) representa o n
umero de
passos utilizados por A com entrada x.
Teorema 4.50. [Algoritmos de Busca Otimos

para NP] Sejam V um verificador eficiente para uma linguagem L NP, q(x) o polinomio que descreve o tamanho dos certificados aceitos por V e p(x) um polinomio que limita a complexidade de tempo de V . Existe
um algoritmo A com as seguintes propriedades:
(i) A resolve o problema de busca associado ao verificador V ;
(ii) Para todo algoritmo A0 que resolve o problema de busca associado ao verificador V
e para toda entrada x {0, 1}? com SV (x) 6= , temos tA (x) = O(tA0 (x) + p(x));
(iii) Para entradas x {0, 1}? com SV (x) = , temos tA (x) = O(2q(|x|) p(|x|)).
Demonstracao. Com entrada x {0, 1}? , o algoritmo A simula em paralelo todos os
algoritmos existentes (explicacoes adiante) e utiliza o algoritmo V para checar a solucao fornecida por cada um deles. Se durante algum passo da simulacao uma solucao
e encontrada, A termina imediatamente sua computacao e imprime a resposta obtida.
Por isso, sempre que A termina sua computacao e imprime uma palavra w, temos que
V (x, w) = 1. Por outro lado, para garantir que A termina sua computacao com entradas

4.7. Algoritmos Otimos
para NP
87
que nao possuem solucao, simulamos tambem em paralelo um algoritmo B que usa uma
busca exaustiva para procurar todos os certificados aceitos pelo verificador V . Podemos
escolher o algoritmo B de modo que tB (x) = O(2q(|x|) p(|x|)).
Suponha que os algoritmos estejam ordenadas de acordo com a ordem lexicografica de
suas descricoes. A simulacao em paralelo realizada por A ocorre por etapas. Na j-esima
etapa de simulacao:
(1) A simula os primeiros 2j 1 algoritmos com entrada x;
(2) O algoritmo Ai e simulado por 2j /(i + 1)2 passos, onde 1 i 2j 1;
Pj
(3) O algoritmo B e simulado por 2i=11 2j /(i + 1)2 passos, ou seja, pelo n
umero total de
passos simulados no item anterior.
A variacao na taxa de simulacao de cada algoritmo sera u
til para provarmos o item (ii)
do teorema. A simulacao do algoritmo B continua na proxima etapa a partir do u
ltimo
passo realizado na etapa anterior. Por outro lado, para nao sobrecarregar o algoritmo A,
as simulacoes do item (2) sao perdidas ao fim de cada etapa. Assumimos que os passos
utilizados para verificacao da solucao obtida pelo algoritmo Ai tambem sao contados na
simulacao realizada em (2).
Devido à simulacao paralela realizada em (3), o algoritmo A sempre termina sua
computacao. Por isso, os itens (i) e (iii) do teorema sao satisfeitos.
Vamos finalmente provar que A satisfaz a segunda propriedade do enunciado. Seja A0
um algoritmo que resolve o problema de busca associado ao verificador V . Alem disso,
suponha que SV (x) 6= . Vamos denotar por t0 (x) = tA0 (x) + p(x) o tempo gasto por A0
para obter uma solucao para a entrada x mais o tempo utilizado por V com a verificacao
0
da solucao obtida. Observe que A0 e no maximo o (2|A |+1 1)-esimo algoritmo segundo a
ordenacao lexicografica adotada. Por isso, os t0 (x) passos necessarios para obter e verificar
a solucao de A0 sao realizados na j-esima etapa de simulacao se:
0
(a) 2j 1 2|A |+1 1, ou seja, j |A|0 + 1; e

0
(b) 2j /(2|A |+1 )2 t0 (x), ou seja, j 2(|A0 | + 1) + log (tA0 (x) + p(|x|).
Portanto, o algoritmo A termina sua computacao com a entrada x na k-esima etapa,

onde k = 2(|A0 | + 1) + log (tA0 (x) + p(|x|). Por isso, o n
umero total de passos simulados
nao e superior a:
j
k 2X
1
X
j=1 i=1
k
k
2X
1
X
2j
1
2 X j+1
0
j+1
2
2
2k+3 = 22|A |+5 [tA0 (x) + p(|x|)].
2
2
(i + 1)
(i + 1)
6 j=1
j=1
i=1
88
P
2
Usamos em uma das desigualdades anteriores o fato de que a serie
e conn=1 1/n
P
2
2
vergente (Rudin [94]). Em particular, temos n=1 1/n = /6. Como assumimos que t
passos podem ser simulados em tempo kt, obtemos que tA (x) = O(tA0 (x) + p(|x|)), como
queramos demonstrar.
Observe que a constante escondida na notacao assintotica depende apenas do algoritmo A0 . Alem disso, essa constante cresce exponencialmente com a descricao de A0 .
Infelizmente, isso faz com que o algoritmo obtido seja inviavel na pratica. No entanto, a
nocao de otimalidade e pontual, ou seja, e valida para cada palavra de tamanho n que
possui solucao, e nao apenas no pior caso.
Mostraremos a seguir que, se a constante anterior fosse apenas polinomial no tamanho
do algoritmo A0 , entao P = NP. Suponha que existisse um polinomio q(.) de forma que
q(|A0 |) limitasse o valor dessa constante. Primeiro, para toda formula proposicional
satisfatvel existe um algoritmo A de tamanho O(|hi|) que, com entrada hi, imprime
uma atribuicao ~y tal que (~y ) = 1 (adicionamos a propria atribuicao ao codigo de A ).
Alem disso, A computa em tempo linear. Portanto, para L = SAT, a complexidade de
tempo do algoritmo obtido na demonstracao anterior seria O(q(|A |)[tA (x) + p(|x|)]),
onde tA (x) e O(x) e |A | e O(|x|). Portanto, poderamos encontrar uma atribuicao
satisfazendo a formula de entrada em tempo polinomial ou determinar que tal atribuicao
nao existe apos a simulacao desse n
umero de passos. Isso provaria que SAT P, e portanto
teramos P = NP.
4.8
Refer
encias Adicionais
A demonstracao do Teorema de Ladner segue o livro de Arora e Barak [7]. Uma

generalizacao desse resultado, aplicavel a` outras classes de complexidade, pode ser obtida no artigo de Schoning [97]. Notamos que um teorema similar existe em teoria da
computabilidade [44, 82].
O teorema 4.50 foi provado por Levin [74]. Veja o artigo de Hutter [60] para uma
extensao desse resultado. Por u
ltimo, o artigo recente de Trevisan [106] discute o tamanho
das constantes envolvidas nessa e em outras demonstracoes similares.
A existencia de problemas completos para todos os nveis de PH foi provada por
Wrathall [113]. Alguns resultados citados neste captulo e outros desenvolvimentos recentes em complexidade computacional sao discutidos no artigo de Cai e Zhu [18].
Diversos temas importantes relacionados com o problema P vs NP nao foram discutidos neste captulo. Em particular, nao abordamos o Teorema PCP (Provas Checaveis
Probabilisticamente). Intuitivamente, esse resultado estabelece que qualquer prova matematica pode ser reescrita com certa redundancia de forma que sua validade possa ser
89
checada em tempo polinomial e com um alto ndice de certeza atraves da leitura de um

n
umero constante de bits escolhidos aleatoriamente. Esse teorema fornece uma nova caracterizacao para a classe NP. Alem disso, ele pode ser usado para provar que, a menos
que P = NP, nao podemos computar eficientemente solucoes aproximadas para diversos
problemas computacionais importantes. Para um excelente tratamento desse topico e
referencias adicionais, consulte o livro de Arora e Barak [7].
Captulo 5
Os Limites da Diagonaliza
c
ao
Oracles are subtle but not malicious.
Scott Aaronson.
Veremos neste captulo que alguns metodos discutidos nesta dissertacao nao
sao capazes de resolver o problema P vs NP. Discutiremos em seguida como
essa limitacao se relaciona com resultados de independencia formal em matematica. Alem disso, vamos estudar o comportamento de diversos problemas
em aberto da complexidade computacional em universos computacionais alternativos. Finalmente, discutiremos como metodos mais modernos superam
a limitacao enfrentada por algumas das tecnicas estudadas anteriormente.
5.1
Introduc
ao
Vimos no captulo 3 que o metodo da diagonalizacao pode ser usado para separar
diversas classes de complexidade interessantes. Em particular, discutimos na secao 3.6
como ele pode ser aplicado, em conjunto com a nocao de completude, para provar que
certos problemas computacionais naturais nao podem ser resolvidos em tempo polinomial.
Alem disso, mostramos em diversas ocasioes que certas inclusoes de classe podem ser
provadas atraves de simulacao.
O principal objetivo deste captulo e demonstrar que essas ideias, emboram sejam
muito poderosas, sao insuficientes para resolver diversas questoes em aberto discutidas
nesta dissertacao. Em particular, mostraremos que nao podemos separar (ou colapsar)
classes como P e PSPACE, NP e coNP, P e PH, e P e NP utilizando apenas simulacao
e diagonalizacao. A principal desvantagem desses metodos e que eles tratam os algo91
92
Captulo 5. Os Limites da Diagonalizacao
ritmos como se fossem caixas-pretas, nao sendo capazes de analisar adequadamente as

computacoes envolvidas.
Informalmente, uma prova utiliza diagonalizacao quando se baseia na enumeracao dos
algoritmos atraves de palavras e na simulacao entre algoritmos sem uma perda significativa
de tempo ou espaco. Geralmente, um algoritmo A ligado a uma classe de complexidade
pode simular todos os algoritmos ligados à outra classe de complexidade mais fraca, negando suas respostas. Por exemplo, poderamos provar o teorema 3.2 dessa forma, e a
linguagem decidida por A seria o complemento da linguagem L definida naquela demonstracao. Veremos uma demonstracao apresentada dessa forma no fim desta secao.
Considere o seguinte argumento utilizado na tentativa de separar as classes de complexidade P e PSPACE.
Exemplo 5.1. [Argumento diagonal envolvendo P e PSPACE]. Vamos tentar descrever
uma MT D que simula todas as maquinas de Turing determinsticas de tempo polinomial,
negando suas respostas. Com entrada hMi i, D computa da seguinte maneira:
1) Simula a maquina Mi com entrada hMi i por (n) passos, onde n = |hMi i| e (.)
e uma funcao a ser definida posteriormente.
2) Se Mi aceita hMi i durante a simulacao, entao D rejeita a entrada hMi i.
3) Caso Mi rejeite hMi i ou nao termine sua computacao em (n) passos, D aceita a
entrada hMi i.
Seja LD a linguagem decidida por D. Queremos provar que LD PSPACE \ P.
Para isso, precisamos mostrar que, para toda MT determinstica que computa em tempo
polinomial, temos L(Mi ) 6= LD . Se Mi computa em tempo ci nci , isso pode ser obtido
se tomarmos (n) ci nci . No entanto, uma MT com essa complexidade de tempo pode
computar em espaco polinomial (nci ). Alem disso, o teorema de hierarquia de tempo
estabelece que a constante ci pode ser arbitrariamente grande para linguagens decidveis
em tempo polinomial. Por isso, ao garantir que LD difere de toda linguagem em P, nao
e possvel provar que D computa em espaco polinomial, i.e., que LD PSPACE. Para
conseguir isso, e preciso que a simulacao realizada na etapa 1 explore alguma propriedade
das computacoes que utilizam espaco polinomial. Porem, e exatamente isso o que queremos provar, ou seja, que essas computacoes sao mais poderosas do que computacoes de
tempo polinomial.
Observe que o metodo da diagonalizacao atrasada (introduzido na prova do teorema
3.34) encontra o mesmo obstaculo, uma vez que precisamos simular entradas de tamanho
n + 1 quando recebemos entradas de tamanho n.
O exemplo anterior mostra que e difcil separar atraves de diagonalizacao classes de
complexidade que utilizam recursos diferentes na mesma proporcao. Para conseguir essa
5.1. Introducao
93
separacao atraves de diagonalizacao e preciso explorar de modo inteligente alguma propriedade do recurso mais poderoso. A mesma dificuldade aparece quando o argumento
anterior e adaptado para as classes P e NP, por exemplo.
Discutimos na secao 4.4 o conceito de maquinas de Turing com acesso a um oraculo.
Vamos a seguir generalizar a definicao 4.29. Se R e uma classe de complexidade e L
{0, 1}? e uma linguagem, denotamos por RL o conjunto de linguagens decidveis por
maquinas de Turing que utilizam uma quantidade de recursos compatvel com a definicao
da classe R e possuem acesso à linguagem L atraves de um oraculo. Por exemplo, NPSAT
denota o conjunto de linguagens decidveis em tempo polinomial nao-determinstico por
maquinas de Turing com acesso a um oraculo para a linguagem SAT.
A adicao de um oraculo a` definicao de uma classe de complexidade cria um novo
universo computacional. Enquanto vivemos em um universo onde nenhuma computacao
ocorre de graca, podemos imaginar mundos em que essa regra e violada. Por exemplo,
NPSAT e uma classe aparentemente mais poderosa do que NP, uma vez que cada caminho
nao-determinstico pode resolver instantaneamente uma instancia de SAT. Utilizando a
completude de SAT e negando a resposta do oraculo, podemos obter a resposta de uma
computacao nao-determinstica baseada em quantificadores universais. Formalmente, e
possvel demonstrar que NPSAT = p2 (veja o livro de Arora e Barak [7], por exemplo).
2
Observamos que muitos textos definem classes de complexidade do tipo RR
1 . Nesse
caso, as maquinas envolvidas podem ter acesso a` qualquer linguagem da classe R2 (a
linguagem e fixa, porem arbitraria). Na maioria dos casos, isso equivale a dizer que
L
2
RR
e uma linguagem completa para a classe R2 .
1 = R1 , onde L
Durante uma simulacao entre maquinas de Turing, todas as chamadas a um oraculo
feitas pela maquina simulada podem ser respondidas pela maquina simuladora, desde que
ela possua acesso ao mesmo oraculo. Veremos a seguir um resultado que utiliza essa
observacao para estender um teorema demonstrado na secao 3.3.
Teorema 5.2. [Diagonalizacao e Oraculos]. Para toda linguagem O {0, 1}? , temos que
PO 6= EXPO .
Demonstracao. Claramente, temos que PO EXPO . Vamos exibir uma maquina de Turing D com acesso ao oraculo O que decide uma linguagem LD tal que LD EXPO \ PO .
Com entrada hMi i, D computa da seguinte forma:
1) Simula 2n passos da computacao da maquina Mi com entrada hMi i, onde n = |hMi i|.
2) Se Mi invoca o oraculo O com uma palavra z na sua fita de oraculo, D obtem a resposta
dessa chamada atraves do seu proprio oraculo para a linguagem O.
3) A maquina D rejeita a entrada hMi i se e somente se Mi aceita hMi i durante a simulacao
anterior.
94
Por construcao, para toda linguagem L PO , existe uma maquina de Turing Mi de

tempo polinomial que decide L tal que hMi i L se e somente se hMi i
/ LD , i.e., L 6= LD .
O
Isso prova que LD
/ P . Alem disso, a maquina determinstica D computa em tempo
exponencial. Portanto, LD EXPO \ PO .
Essencialmente, o oraculo O nao possui nenhuma influencia na prova do resultado
anterior. Por isso, dizemos que a demonstracao e insensvel à presenca de um oraculo.
Em outras palavras, demonstracoes que envolvem apenas simulacao entre algoritmos e
diagonalizacao provam resultados que sao validos em todos os universos computacionais
possveis. Em complexidade computacional, dizemos que provas e metodos com essa
propriedade relativizam, i.e., demonstram resultados verdadeiros em relacao à qualquer
oraculo.
O leitor pode verificar que todas as demonstracoes apresentadas no captulo 3 sao
indiferentes a` presenca de oraculos. Portanto, em qualquer universo computacional, esses
resultados sao verdadeiros. Veremos na secao 5.2 que e exatamente por isso que esses
metodos sao incapazes (sem nenhum argumento adicional que nao relativize) de resolver
o problema P vs NP. Vamos exibir dois mundos computacionais distintos onde P = NP e
P 6= NP, respectivamente.
5.2
Uma Barreira Fundamental
Nesta secao vamos provar que existem linguagens A, B {0, 1}? tais que PA = NPA
e PB 6= NPB . Esse resultado foi provado por Baker, Gill e Solovay [8]. Como provas por
simulacao e diagonalizacao demonstram resultados validos em qualquer universo computacional, isso mostra que esses metodos nao sao suficientes para resolver o problema P vs
NP.
Teorema 5.3. [Teorema de Relativizacao BGS]. Existem linguagens A, B {0, 1}? tais
que PA = NPA e PB 6= NPB . Alem disso, temos que A,B EXP.
Demonstracao. Seja A uma linguagem PSPACE-completa. Claramente, usando simulacao temos que PA = PSPACE = NPA . Pelo lema 3.9, obtemos que A EXP.
Precisamos agora demonstrar a existencia de linguagens B e LB tais que LB NPB \ PB .
Para toda linguagem B {0, 1}? , seja LB a seguinte linguagem unaria:
LB = {1n : w {0, 1}n tal que w B}.
Observe que, para toda linguagem B, temos que LB NPB (um verificador eficiente
com acesso à B pode usar w como certificado de que 1n LB ). Resta demonstrar que
LB
/ PB . Para obter isso, vamos definir B em etapas, de modo que essa linguagem
5.2. Uma Barreira Fundamental
95
seja uma adversaria para qualquer maquina de Turing de tempo polinomial com acesso
ao oraculo B que tenta decidir LB . Considere que M1 , M2 , . . . e uma lista de todas as
maquinas de Turing, de forma que cada maquina de Turing apareca infinitas vezes nessa
enumeracao.
Ate o incio da etapa i, a pertinencia em B de apenas uma quantidade finita de
palavras foi determinada. Note que isso vale no incio da etapa 1, quando B e totalmente
indeterminada. Seja n i o menor n
umero inteiro de forma que a presenca em B
de nenhuma palavra de tamanho maior ou igual a n tenha sido decidida. Considere
a computacao de ate 2n1 passos da maquina de Turing Mi com entrada 1n (Mi pode
terminar sua computacao antes de completar 2n1 passos). Se a maquina Mi indaga sobre
a presenca em B de uma palavra w ja determinada, respondemos consistentemente. Se
a presenca de w ainda nao foi decidida, respondemos negativamente e determinamos que
w
/ B. Por u
ltimo, se em 2n1 passos a maquina Mi aceita a entrada 1n , determinamos
que todas as palavras restantes de tamanho menor ou igual a n ainda nao consultadas
nao pertencem à linguagem B. Caso contrario, decidimos que essas palavras estao em B.
Isso completa a descricao da linguagem B.
Note que se Mi aceita 1n em ate 2n1 passos, entao nao existe palavra de tamanho
n que pertence a` B, ou seja, 1n
/ LB . Por outro lado, se a palavra 1n nao e aceita por
Mi em ate 2n1 passos, pelo menos metade das palavras de tamanho n estao em B, uma
vez que em 2n1 passos B so pode ter usado o oraculo para verificar a pertinencia de ate
2n1 palavras. Por isso, neste caso temos que 1n LB . Isso mostra que se Mi termina
sua computacao com a entrada 1n em ate 2n1 passos, entao Mi nao decide LB .
Seja M uma maquina de Turing que computa em tempo polinomial. Entao existe um
inteiro positivo n0 tal que, para toda palavra w de tamanho n0 n0 , M aceita ou rejeita
0
w em no maximo 2n 1 passos. Lembre que cada maquina de Turing aparece infinitas
vezes na enumeracao adotada. Portanto, existe um ndice i n0 tal que M e equivalente
a Mi . Alem disso, na i-esima etapa de construcao da linguagem B, tomamos n i n0
e garantimos que se Mi computa em tempo 2n1 com a entrada 1n , entao L(Mi ) 6= LB .
Portanto, M nao decide a linguagem LB . Isso prova que nao existe maquina de Turing
de tempo polinomial com acesso ao oraculo B que decide LB , ou seja, LB
/ PB .
Observe que, como tomamos na i-esima etapa n i, a presenca em B de palavras de
tamanho menor ou igual a n e determinada pelo comportamento das primeiras i maquinas
de Turing. Portanto, para decidir se uma palavra w de tamanho n pertence a` B, basta
simularmos a computacao das primeiras i maquinas de Turing, onde i n e a i-esima
maquina nunca precisa ser simulada por mais do que 2n1 passos. Como isso pode ser
feito em tempo exponencial, temos que B EXP, como queramos demonstrar.
O teorema anterior nos da forte evidencia de que, para resolver o problema P vs NP,
precisamos investigar profundamente as computacoes envolvidas, e nao apenas simula-
96
interessante notar que provamos que a diagonalizacao e uma tecnica fraca contra o
las. E
problema P vs NP utilizando basicamente um argumento por diagonalizacao.
Podemos estudar os oraculos em situacoes muito mais complexas. Por exemplo, existe
algum universo computacional onde NP = coNP, mas P 6= NP? Vamos enunciar diversos
resultados desse tipo na secao 5.4.
5.3
P vs NP e Resultados de Independ
encia
Quais as implicacoes do Teorema BGS para o problema P vs NP? Nesta secao vamos
discutir algumas questoes envolvendo oraculos e resultados de independencia em matematica.
Dizemos que uma proposicao matematica e independente de um conjunto de axiomas
A se tanto quanto nao podem ser provadas a partir de A. Em primeiro lugar,
como isso pode ser possvel? Inicialmente, vamos discutir a diferenca entre verdade e
demonstrabilidade.
A nocao de verdade nunca esta relacionada com um conjunto de axiomas, mas sim
com uma determinada estrutura que satisfaz os axiomas adotados. Por exemplo, dados
os axiomas da teoria de grupos, um grupo arbitrario G1 e uma estrutura que satisfaz
tais axiomas. Seja uma formula que expressa que um grupo e comutativo, ou seja,
xy(xy = y x). A formula pode ser verdadeira para alguns grupos e falsa em relacao
a outros grupos. Portanto, a nocao de verdade depende da estrutura em consideracao.
Por outro lado, o conceito de demonstrabilidade depende apenas dos axiomas e das
regras de derivacao de um sistema formal. Uma formula pode ser provavel a partir
de um conjunto de axiomas A (e de certas regras de derivacao) ou nao. Um fato muito
importante dos sistemas formais utilizados em matematica e que eles sao corretos, ou
seja, sempre que uma formula e demonstravel a partir de um conjunto de axiomas,
ela e verdadeira em qualquer estrutura que satisfaca os axiomas. Por exemplo, quando
provamos um teorema a partir dos axiomas da teoria de grupos, sabemos que todo
grupo (i.e., estrutura compatvel com esses axiomas) satisfaz a proposicao . Devido a`
corretude, se existem duas estruturas diferentes que satisfazem certos axiomas, mas que
nao concordam em relacao a uma certa propriedade expressa por uma formula (em uma
estrutura a propriedade e verdadeira e em outra nao), entao temos que tanto quanto
sao formulas que nao podem ser provadas a partir de tais axiomas. Portanto, dados
certos axiomas, e possvel que uma proposicao seja verdadeira (em relacao a uma estrutura
canonica que associamos ao sistema formal1 ), porem nao seja demonstravel.
1
Por exemplo, associamos `

as diversas regras da aritmetica a estrutura canonica formada pelo conjunto
de n
umeros inteiros. No entanto, existem diversas estruturas bastante distintas que satisfazem os mesmos
axiomas.
5.3. P vs NP e Resultados de Independencia
97
Embora tenhamos discutido apenas informalmente esses conceitos, a distincao precisa

entre verdade e demonstrabilidade provocou uma revolucao na matematica durante o
seculo passado. Notamos que a relacao entre esses dois conceitos depende tambem do
poder expressivo das formulas utilizadas para expressar as proposicoes matematicas.
Lembre que a teoria de conjuntos ZFC foi discutida na secao 2.6, e que com esse sistema formal podemos provar todos os teoremas usuais demonstrados em matematica. No
entanto, e possvel demonstrar que certas questoes bastante profundas sao independentes
desses axiomas. Por exemplo, embora a questao P vs NP seja verdadeira ou falsa (as duas
classes coincidem ou nao no modelo padrao de ZFC), pode ser que a relacao entre as duas
classes nao possa der decidida (atraves de uma demonstracao) dentro do sistema formal
ZFC.
Intuitivamente, o teorema BGS pode ser visto como um mini-resultado de independencia. Essencialmente, ele prova que o problema P vs NP e independente de qualquer
teoria matematica que prove apenas resultados que relativizam, ou seja, que sao validos na
presenca de qualquer oraculo. Embora muitos metodos discutidos nesta dissertacao nao
sejam capazes de ultrapassar a barreira imposta pelo teorema BGS, existem tecnicas mais
modernas que nao possuem essa limitacao. Apresentaremos na secao 5.8 uma discussao
adicional sobre isso. Assim, tendo em vista a existencia de metodos capazes de superar
essa dificuldade, nao podemos tirar ainda nenhuma conclusao a` respeito da independencia
do problema P vs NP original em relacao à sistemas fortemente expressivos como a teoria
de conjuntos ZFC.
No entanto, veremos nesta secao que, de fato, existem certos resultados em complexidade computacional que sao independentes dos axiomas usuais da matematica. Vamos
demonstrar que existe uma maquina de Turing M tal que o problema PL(M ) vs NPL(M ) e
independente de ZFC. Isso ilustra as sutilezas envolvidas quando abandonamos o mundo
real e estudamos universos relativizados.
Teorema 5.4. Existe uma maquina de Turing determinstica M que sempre termina sua
computacao tal que o problema PL(M ) vs NPL(M ) e independente de ZFC. Alem disso,
temos que L(M ) = .
Demonstracao. Vamos utilizar na demonstracao o teorema da recursao, um resultado que
garante que podemos alterar toda maquina de Turing de modo que seu proprio codigo
esteja disponvel durante a computacao. Veja o livro de Sipser [103] para mais detalhes.
De acordo com o teorema 5.3, existem linguagens decidveis A e B tais que PA = NPA
e PB 6= NPB . Alem disso, e possvel mostrar que esse teorema pode ser provado dentro
do sistema formal ZFC. Seja M uma maquina de Turing que aceita uma entrada x se e
somente se:
98
1) x A e existe uma prova de tamanho no maximo |x| em ZFC de que PL(M ) =

6 NPL(M ) ;
ou
2) x B e existe uma prova de tamanho no maximo |x| em ZFC de que PL(M ) = NPL(M ) .
Na descricao anterior, a maquina de Turing M tem disponvel seu proprio codigo para
construir uma formula que expressa PL(M ) = NPL(M ) .
Suponha que PL(M ) = NPL(M ) seja provavel em ZFC. Por construcao, a menos de um
n
umero finito de palavras, temos que L(M ) = B. Por isso, ZFC tambem demonstra que
PB = NPB . No entanto, isso viola a consistencia dessa teoria, uma vez que ZFC prova que
PB 6= NPB . Portanto, nao existe demonstracao em ZFC de que PL(M ) = NPL(M ) . Similarmente, a menos que ZFC seja inconsistente, nao existe prova de que PL(M ) 6= NPL(M )
dentro desse sistema formal. Isso mostra que a relacao entre as classes PL(M ) e NPL(M )
nao pode ser determinada em ZFC.
Por u
ltimo, observe que como PL(M ) = NPL(M ) e independente de ZFC, segue a partir
da definicao de M que L(M ) = .
O teorema 5.4 foi provado por Hartmanis e Hopcroft [52]. No mesmo artigo sao
exibidos alguns algoritmos cuja complexidade de tempo e independente de ZFC. Notamos
que L(M ) = nao implica que o problema P vs NP original seja independente de ZFC.
Pode nao ser possvel provar dentro desse sistema que as classes P e PL(M ) sao equivalentes,
por exemplo. Em particular, se ZFC fosse capaz de provar que L(M ) = , entao ZFC
provaria sua propria consistencia (veja a definicao da maquina de Turing M ), o que violaria
um resultado importante da logica matematica.
O resultado de independencia anterior e baseado na maquina de Turing M . Existem
maquinas de Turing muito mais simples que decidem a linguagem vazia, e nao esta claro
se o mesmo resultado de independencia pode ser provado quando substituimos M por tais
maquinas. Afinal de contas, nao sabemos realmente se o problema P vs NP original e
independente de ZFC. No entanto, existe um oraculo decidvel O tal que o problema PO
vs NPO e independente de ZFC em relacao a qualquer maquina de Turing utilizada para
representar O. Veja o artigo de Kurtz et al. [72] para mais detalhes.
Finalmente, notamos que a maioria dos pesquisadores acredita que questoes combinatoriais como o problema P vs NP nao sao independentes dos axiomas usuais da matematica. Veja diversos pontos de vista interessantes sobre essa questao no artigo de Gasarch
[46].
5.4. Resultados Adicionais
5.4
99
Resultados Adicionais
Nesta secao veremos que existem universos computacionais onde as mais variadas situacoes envolvendo classes de complexidade podem acontecer. Embora tais resultados
indiquem que nao devemos esperar por solucoes simples para muitas questoes em complexidade computacional, eles podem nos fornecer algumas informacoes interessantes. Por
exemplo, considere o seguinte problema em aberto.
Quest
ao em Aberto 5.5. Se P = NP, entao P = PSPACE ?
Considere a seguinte abordagem para provar esse resultado. Vimos na secao 4.2 que
a classe PSPACE contem as linguagens decidveis por maquinas de Turing de tempo
polinomial com um n
umero arbitrario de alternancias (veja o corolario 4.19). Poderamos
utilizar a hipotese de que P = NP e simulacao para eliminar cada alternancia, uma de cada
vez, sem aumentar muito a complexidade da maquina de Turing obtida. Isso provaria que
P = PSPACE.
Embora seja bastante intuitiva, essa abordagem nao e viavel. Isso se deve ao seguinte
teorema.
Teorema 5.6. Existe um oraculo A tal que PA = NPA e NPA 6= PSPACEA .
Demonstracao. Veja o artigo de Ko [68].
Portanto, qualquer prova da questao em aberto 5.5 envolvendo apenas simulacao poderia
ser usada para demonstrar tambem que se PA = NPA , entao PA = PSPACEA , contradizendo o teorema 5.6. Na verdade, um resultado mais geral foi provado por Ko [68].
Teorema 5.7. [Oraculos e a Hierarquia Polinomial]. Para todo inteiro k 0, existem
oraculos A e B tais que:
(i) PHA = pk A e PHA 6= PSPACEA .
(ii) PHB = pk B e PHB = PSPACEB .
O teorema 5.6 fica demonstrado quando tomamos k = 0. Em particular, o teorema
anterior mostra que nao podemos separar ou colapsar os nveis da hierarquia polinomial
atraves de uma demonstracao que envolva apenas simulacao e diagonalizacao.
Vamos enunciar a seguir diversos resultados envolvendo oraculos. A maioria dos oraculos sao construdos por etapas usando diagonalizacao, como na prova do teorema 5.3.
Alguns deles precisam satisfazer diversos requisitos simultaneamente, o que torna as demonstracoes um pouco mais complicadas. Por simplicidade, as provas foram omitidas.
O proximo resultado mostra que, em universos relativizados, as mais diversas situacoes
podem ocorrer envolvendo as classes P, NP e coNP.
100
Teorema 5.8. [P, NP, coNP e Relativizacao]. Existem oraculos A,B e C tais que:
(i) PA 6= NPA coNPA e NPA coNPA 6= NPA .
(ii) PB 6= NPB e NPB = coNPB .
(iii) PC = NPC coNPC e NPC coNPC 6= NPC .
Demonstracao. Veja o artigo original sobre relativizacao de Baker, Gill e Solovay [8].
posVimos na secao 2.8 que se P = NP, entao EXP = NEXP (teorema 2.30). E
svel provar a equivalencia entre essas duas afirmacoes? Utilizando apenas simulacao e
diagonalizacao, a resposta e negativa.
Teorema 5.9. Existe um oraculo A tal que PA 6= NPA e EXPA = NEXPA .
Demonstracao. Veja o artigo de Dekhtyar [32].
Alem disso, nesse mesmo artigo e demonstrado que existem oraculos que separam as
classes PSPACE e EXP.
Discutimos na secao 4.6 a conjectura do isomorfismo. Notamos que e possvel construir
um oraculo que da origem a um universo computacional onde essa conjectura e verdadeira.
Veja o artigo de Fenner et al. [35] para mais detalhes. Entretanto, veremos na proxima
secao que a conjectura do isomorfismo e falsa na maioria dos universos computacionais
relativizados.
Em suma, resultados envolvendo oraculos servem como um guia para as pesquisas atuais. Precisamos descobrir metodos que nao relativizam se quisermos resolver os problemas
em aberto mais importantes da teoria de complexidade computacional.
5.5
Or
aculos Aleat
orios
Considere a seguinte particao da classe de linguagens: A = {L {0, 1}? : PL = NPL }

e B = {L {0, 1}? : PL 6= NPL }. Qual desses conjuntos e maior? Existe alguma relacao
entre essa questao e o problema P vs NP original?
Para formalizar a primeira questao, definimos um espaco de probabilidade no conjunto
de oraculos C = {L : L {0, 1}? }. Para isso, escolhemos os oraculos de modo aleatorio2 ,
de forma que cada palavra x pertenca ou nao ao oraculo de modo independente e com
probabilidade 1/2. Portanto, a primeira questao discutida no paragrafo anterior pode ser
enunciada da seguinte maneira: qual a probabilidade (medida) do conjunto A?
2
Formalmente, para estudar as probabilidades no conjunto infinito C precisamos de diversas definicoes

de uma disciplina matem
atica conhecida como teoria da medida . Por simplicidade, vamos discutir todos
os resultados desta sec
ao de modo informal. O leitor interessado pode consultar o livro de Du e Ko [33].
5.5. Oraculos Aleatorios
101
Existe um resultado em teoria da medida conhecido como lei zero-um que garante
que, para praticamente qualquer propriedade S envolvendo oraculos, S ocorre com probabilidade um ou com probabilidade zero. Em particular, sabemos que Prob(A) = 1 ou
Prob(A) = 0. No entanto, qual dos dois casos e verdadeiro3 ? Bennett e Gill [10] demonstraram que, em praticamente todos os universos computacionais possveis, as classes P e
NP sao distintas.
Teorema 5.10. [P vs NP e Oraculos Aleatorios].
ProbC [PL 6= NPL ] = 1.
Demonstracao. A prova desse resultado considera a linguagem L0 = {0n : w {0, 1}n tal
que w1, w11, . . . , w1n L}. Em primeiro lugar, w serve como certificado de que 0n L0
(o verificador tem acesso ao oraculo L). Portanto, para toda linguagem L, temos que
L0 NPL . Por outro lado, e possvel demonstrar que a probabilidade de L0 ser decidida
por uma maquina de Turing determinstica de tempo polinomial com acesso a` L e zero.
Uma prova completa desse resultado pode ser obtida no livro de Du e Ko [33].
Corol
ario 5.11. Existe um oraculo B tal que PB 6= NPB .
possvel demonstrar que no espaco dos oraculos C a conjectura do isomorfismo e
E
falsa com probabilidade um. Em outras palavras, o conjunto I = {L C : A conjectura
do isomorfismo e verdadeira em NPL } possui medida zero. Esse resultado foi provado por
Kurtz et al. [71].
Finalmente, o que podemos deduzir sobre os problemas originais a partir desses resultados envolvendo oraculos aleatorios? Essa questao levou Bennet e Gill [10] a formularem
a Hipotese do Oraculo Aleatorio:
Se um resultado em complexidade computacional e verdadeiro com probabilidade um para
oraculos aleatorios, entao ele e verdadeiro no universo nao-relativizado.
Se essa hipotese e verdadeira, entao o teorema 5.10 prova que P 6= NP. Alem disso, a
conjectura do isomorfismo seria falsa. No entanto, Kurtz [70] demonstrou que a Hipotese
do Oraculo Aleatorio e falsa. Diversos contra-exemplos adicionais foram obtidos posteriormente [21, 51]. Isso significa que nao e possvel extrair nenhuma relacao entre o teorema
5.10 e a questao P vs NP original.
Finalmente, notamos que os resultados envolvendo oraculos aleatorios sao u
teis na
criacao de universos computacionais onde diversas situacoes ocorrem simultaneamente.
Por exemplo, no espaco dos oraculos C temos com probabilidade um que NP 6= PSPACE
3
Esse fato n
ao contradiz o teorema BGS, uma vez que em espacos infinitos eventos com probabilidade
zero podem ocorrer.
102
e PSPACE ( EXP (veja o livro de Du e Ko [33]). Portanto, existe uma linguagem L tal
que NPL 6= PSPACEL e PSPACEL ( EXPL .
5.6
Relativizac
ao Positiva
Nesta secao vamos discutir uma modificacao na definicao da classe de complexidade

NP relativizada. Veremos que o teorema BGS nao pode ser provado com a alteracao
introduzida. O tipo de relativizacao resultante e conhecida como relativizacao positiva.
Na demonstracao do teorema BGS, podemos converter o verificador eficiente apresentado para a linguagem LB em uma maquina de Turing nao-determinstica M que computa
em tempo polinomial (veja a prova do teorema 2.17). Alem disso, note que a maquina M
precisa realizar apenas uma chamada ao oraculo B em cada um dos 2n caminhos de sua
arvore de computacao.
Observe que enquanto os algoritmos determinsticos de tempo polinomial que tentam
decidir LB podem fazer apenas uma quantidade polinomial de perguntas ao oraculo B,
os algoritmos nao-determinsticos de tempo polinomial podem realizar um n
umero exponencial de chamadas ao mesmo oraculo. Por isso, a definicao do mecanismo de acesso
aos oraculos permite que MTNDs obtenham uma quantidade exponencial de informacoes
sobre a linguagem B, o que naturalmente as torna mais poderosas do que as maquinas
determinsticas. Para comparar de forma mais justa a relacao entre computacao determinstica e nao-determinstica em um universo relativizado, devemos garantir que os dois
modelos tenham acesso a` mesma quantidade de informacoes.
Definic
ao 5.12. [Relativizacao Positiva]. Para todo oraculo O {0, 1}? , denotamos por
NPO
veis por MTNDs de tempo polinomial que realizam
+ o conjunto de linguagens decid
uma quantidade total de chamadas ao oraculo O limitada por um polinomio no tamanho
da entrada.
Interessantemente, quando adicionamos essa restricao a` classe NP relativizada, podemos provar que o problema P vs NP original e independente do universo computacional
em consideracao.
Teorema 5.13. [P vs NP e Relativizacao Positiva].
P = NP se e somente se, para todo oraculo O {0, 1}? , temos que PO = NPO
+.
possvel demonstrar a parte nao-trivial desse teorema atraves de uma
Demonstracao. E
ideia similar àquela utilizada na prova do teorema de Mahaney (secao 4.46). A demonstracao original pode ser obtida no artigo de Brook et al. [13].
Portanto, as restricoes de acesso ao oraculo tem um papel central na definicao de classes
de complexidade relativizadas. Levando em conta o teorema anterior, podemos concluir
5.7. O Argumento Contrario de Kozen
103
que o teorema BGS e os outros resultados envolvendo relativizacao nao sao interessantes?
Como vimos nas secoes anteriores, esses teoremas sao essenciais para demonstrarmos que
atraves de simulacao e diagonalizacao nao podemos resolver diversos problemas importantes em complexidade computacional.
5.7
O Argumento Contr
ario de Kozen
Veremos agora um resultado que parece contradizer o argumento apresentado neste

captulo de que uma prova envolvendo apenas diagonalizacao nao pode separar as classes
P e NP.
Um pouco apos a demonstracao do teorema BGS, Dexter Kozen [69] publicou um
artigo bastante controverso em que ele argumenta que se existe uma demonstracao de que
P 6= NP, entao existe uma demonstracao por diagonalizacao4 .
Definic
ao 5.14. [Linguagem Diagonal de uma Funcao]. Seja M1 , M2 , . . . uma enumeracao das maquinas de Turing determinsticas de tempo polinomial. Seja h : {0, 1}? N
uma funcao arbitraria. Dizemos que diagh e a linguagem diagonal da funcao h se diagh =
{x {0, 1}? : Mh(x) rejeita a entrada x}.
Em seu artigo, Kozen mostrou que as linguagens utilizadas na demonstracao dos teoremas de hierarquia originais sao linguagens diagonais de determinadas funcoes computaveis. No entanto, os argumentos de Kozen sao mais gerais e podem ser usados para
provar certas consequencias intrigantes.
Lema 5.15. Seja h : {0, 1}? N uma funcao arbitraria. A linguagem diagh
/ P se:
(i) Para toda linguagem L P, existe uma palavra x tal que L = L(Mh(x) ); ou
(ii) Para toda linguagem L P, existe uma linguagem L0 que difere de L em apenas um
n
umero finito de palavras tal que, para infinitas palavras x, temos que L0 = L(Mh(x) ).
Demonstracao. Vamos provar que se qualquer uma das condicoes for satisfeita, entao
diagh
/ P. Suponha que diagh P, ou seja, existe L P tal que diagh = L.
Assuma que a primeira condicao do lema seja valida. Entao existe w {0, 1}? tal
que diagh = L(Mh(w) ). Logo, w diagh se e somente se w L(Mh(w) ). Por sua vez,
w L(Mh(w) ) se e somente se Mh(w) aceita w. Pela definicao de diagh , essa u
ltima
condicao ocorre se e somente se w
/ diagh . Essa contradicao mostra que diagh
/ P.
Por u
ltimo, assuma que a segunda condicao do lema seja verdadeira. Seja L0 uma
linguagem satisfazendo as hipoteses do lema. Como diagh e L0 diferem apenas em uma
4
Em seu artigo original, uma teoria mais geral e desenvolvida. Nesta secao vamos discutir apenas os
aspectos relacionados com o problema P vs NP.
104
quantidade finita de palavras, existe uma palavra w tal que w diagh se e somente se
w L(Mh(w) ). Como no caso anterior, obtemos uma contradicao. Isso completa a prova
de que diagh
/ P.
Teorema 5.16. [Classe P e Linguagens Diagonais]. Para toda linguagem L
/ P, existe
uma funcao computavel h tal que L = diagh . Alem disso, h pode ser escolhida de forma
que as duas condicoes do lema 5.15 sejam satisfeitas.
Demonstracao. Consulte o artigo original de Kozen [69].
Corol
ario 5.17. P 6= NP se e somente se SAT = diagh , onde h e uma funcao computavel
que satisfaz as duas condicoes do lema 5.15.
Devido ao corolario anterior, Kozen conclui que se P 6= NP e demonstravel, entao isso
pode ser feito atraves de uma prova por diagonalizacao (corolario 6.2 do artigo [69]). O
que podemos concluir a partir dessa afirmacao aparentemente contraditoria?
Fortnow [39] argumenta que o principal problema com a interpretacao original de
Kozen e que o conceito de prova por diagonalizacao nao esta definido. No entanto, vamos
pensar um pouco mais sobre o enunciado do corolario 5.17. Note que, assumindo que
P 6= NP, obtemos que SAT
/ P. Por isso, o teorema 5.16 pode ser aplicado, mostrando que
existe uma funcao h computavel tal que SAT = diagh . Isso prova que podemos separar
P e NP utilizando diagonalizacao? Nao, pois assumimos a hipotese de que P 6= NP
para produzir uma funcao h com as propriedades desejadas. Nada garante que a prova
original que separa as classes P e NP utiliza diagonalizacao. Portanto, embora o teorema
demonstrado por Kozen seja interessante, a interpretacao original dos resultados nao
parece estar correta.
5.8
Possvel Superar a Relativiza

E
c
ao?
Vimos nas secoes anteriores que a resposta para diversas questoes em aberto da teoria de complexidade computacional depende do universo computacional em consideracao.
Mostramos tambem que as provas envolvendo apenas diagonalizacao e simulacao relativizam, ou seja, provam resultados que sao validos na presenca de qualquer oraculo. Em
particular, diversos metodos discutidos nesta dissertacao nao sao capazes de resolver o
problema P vs NP.
Apos a demonstracao do teorema BGS, as pesquisas em complexidade computacional
se concentraram na busca por metodos capazes de superar a relativizacao. Uma possibilidade e utilizar problemas completos nas demonstracoes. Por exemplo, a prova do teorema
de Ladner (teorema 4.34) nao pode ser estendida trivialmente para qualquer oraculo O.
A demonstracao desse resultado utiliza a linguagem SAT, que e completa para a classe
Possvel Superar a Relativizacao?

5.8. E
105
NP. Para generalizar esse resultado, precisamos substitu-la por uma linguagem completa
para NPO . Nesse caso, linguagens dessa forma poderiam ser obtidas, de modo similar
a`quele usado na demonstracao do teorema 2.22.
A relativizacao das tecnicas baseadas em simulacao e diagonalizacao indica que para
resolver o problema P vs NP devemos de fato analisar as computacoes envolvidas, e
nao apenas simula-las. Como vimos na secao 2.7, uma das abordagens propostas foi a
utilizacao de metodos combinatoricos baseados na complexidade de circuitos.
Por qual motivo esses metodos nao foram capazes de resolver a questao P vs NP? Em
1994, Razborov e Rudich [90] apresentaram uma limitacao crucial para as abordagens
envolvendo limitantes inferiores no tamanho dos circuitos. Eles definiram a nocao de
prova matematica natural, mostrando que todas as abordagens por circuitos utilizadas
ate entao satisfaziam esse conceito. Em seguida, provaram que se fosse possvel obter um
limitante inferior forte com tais provas matematicas, isso violaria uma forma mais forte
da conjectura P vs NP que muitos pesquisadores acreditam ser verdadeira.
A classe de complexidade IP contem as linguagens que admitem provas interativas
eficientes. Para uma definicao precisa, veja o livro de Goldreich [47]. Fortnow e Sipser
[43] demonstraram que em certos universos relativizados, algumas linguagens em PSPACE nao possuem provas interativas eficientes, ou seja, existe um oraculo A tal que
IPA 6= PSPACEA . Portanto, qualquer demonstracao de que IP = PSPACE precisaria
utilizar alguma tecnica nova. No mesmo artigo, Fortnow e Sipser conjecturaram que as
classes IP e PSPACE sao diferentes.
Em 1992, A. Shamir [101] surpreendeu a comunidade cientfica ao demonstrar que
ocorre o colapso entre essas duas classes, ou seja, IP = PSPACE. Sua prova utiliza novas
ideias algortmicas baseadas em metodos algebricos, capazes de superar a barreira imposta
pela existencia de um mundo relativizado contraditorio. A grande novidade utilizada na
demonstracao foi a aritmetizacao de certas formulas logicas basedas em um problema
completo para a classe PSPACE.
Em 1998, Buhrman et al. [17] demonstraram a primeira separacao de classes de complexidade que nao relativiza. O resultado obtido por esses pesquisadores mostra que
podemos separar classes de complexidade atraves de diagonalizacao se utilizarmos na demonstracao algum resultado que nao relativiza. O argumento nao-relativizante utilizado
nessa prova tambem e baseado em metodos algebricos. Portanto, ainda que a tecnica de
diagonalizacao por si so possua muitas limitacoes, quando combinada com outros metodos
que nao relativizam, ela continua capaz de provar resultados interessantes em complexidade computacional.
possvel resolver o problema P vs NP atraves dessas novas tecnicas algebricas? Em
E
2008, Aaronson e Wigderson [5] mostraram que esses metodos tambem nao sao suficientes,
e que diversos resultados importantes, como o ja citado IP = PSPACE, possuem uma
106
propriedade essencial que os tornam compatveis com tais metodos. Por outro lado, e
possvel provar que o problema P vs NP e resistente ao uso dessas tecnicas.
Resumindo, e possvel superar a relativizacao. No entanto, assim como ocorre com
o metodo da diagonalizacao e simulacao, diversas barreiras foram descobertas para as
tecnicas mais recentes. Por um lado, a possibilidade de provar que determinados metodos nao sao capazes de resolver certos problemas e um aspecto fascinante da teoria de
complexidade computacional. Por outro, isso mostra que precisamos de novas ideias para
resolver os problemas em aberto mais importantes na area.
5.9
Refer
encias Adicionais
Diversos topicos discutidos neste captulo sao abordados nos artigos de Fortnow [38, 39]
e no livro de Du e Ko [33]. Consulte esses textos para mais detalhes.
O artigo de Joseph e Young [63] discute a possibilidade da independencia formal de
certas questoes em ciencia da computacao. O artigo de Ben-David e Halevi [9] aborda
a independencia do problema P vs NP. Alem desses textos, recomendamos fortemente a
leitura do artigo de Aaronson [2].
Diversos resultados adicionais envolvendo relativizacao positiva aparecem no artigo de
Book et al. [13]. Para saber mais sobre oraculos aleatorios, leia o artigo de Vollmer e
Wagner [108]. Por u
ltimo, um trabalho relativamente recente de Remmel et al. [83] discute
certas questoes relacionadas com os resultados de Kozen [69] envolvendo diagonalizacao.
Captulo 6
Conclus
ao
Em complexidade computacional existem mais perguntas intrigantes do que respostas.
Como provar que P 6= NP? Quais sao os limites da computacao eficiente? Qual a relacao
entre determinismo e nao-determinismo? A complexidade computacional nao e uma disciplina sobre computadores, mas sim sobre computacao. Infelizmente, nao sabemos muito
sobre esse conceito.
Vimos no incio desta dissertacao que, para mostrar que certos algoritmos nao existem,
precisamos de uma demonstracao matematica. No entanto, na maior parte do texto, o que
usamos realmente de matematica, alem de raciocnio logico? Essencialmente, construmos
novos algoritmos para provar que certos algoritmos nao existem, deixando de lado teorias
e teoremas matematicos mais avancados.
Discutimos os teoremas de hierarquia na secao 3.2. A prova desses teoremas utiliza
um argumento de diagonalizacao muito simples. Analisando a essencia desses resultados, notamos que eles estabelecem o fato fundamental de que nao e possvel acelerar a
computacao de maquinas de Turing universais. Pode parecer ridculo, mas dado nosso
conhecimento atual, sem diagonalizacao a principal questao em aberto da teoria de complexidade computacional seria: existe alguma linguagem que nao pode ser decidida em
tempo linear?
Felizmente, sabemos mais do que isso. Alem disso, olhando para certos universos
computacionais alternativos, fomos capazes de perceber que apenas simulacao e diagonalizacao nao sao suficientes para resolver diversos problemas importantes. Estimulados por
esse resultado, descobrimos novos metodos, assim como novas barreiras.
Todas essas limitacoes sugerem que o problema P vs NP e sutil demais para as tecnicas
bem provavel que seja preciso utilizar metodos muito mais avancados para
conhecidas. E
resolver esse problema. Vimos na secao 2.7 que abordagens mais recentes sao baseadas
muito difcil prever quando respostas definitivas serao encontradas. A
nessa intuicao. E
u
nica certeza e que muitas surpresas e resultados extraordinarios estao por vir.
107
Refer
encias Bibliogr
aficas
[1] S. Aaronson. The complexity zoo. Disponvel em http://qwiki.caltech.edu/wiki/
ComplexityZoo.
[2] S. Aaronson. Is P Versus NP Formally Independent?
81:109136, 2003.
Bulletin of the EATCS,
[3] S. Aaronson. The prime facts: From Euclid to AKS, 2003. Disponvel em http:
//www.scottaaronson.com/writings/prime.pdf.
[4] S. Aaronson. Guest Column: NP-complete problems and physical reality. ACM
SIGACT News, 36(1):3052, 2005.
[5] S. Aaronson e A. Wigderson. Algebrization: A new barrier in complexity theory.
ACM Transactions on Computation Theory, 1(1):2, 2009.
[6] M. Agrawal, N. Kayal, e N. Saxena. PRIMES is in P. Annals of Mathematics,
paginas 781793, 2004.
[7] S. Arora e B. Barak. Computational Complexity: A Modern Approach. Cambridge
University Press, New York, NY, 2009.
[8] T. Baker, J. Gill, e R. Solovay. Relativizations of the P =? NP Question. Journal
of the ACM, 42:401420, 1975.
[9] S. Ben-David e S. Halevi. On the independence of P versus NP. Relatorio tecnico,
Relatorio Tecnico.
[10] C.H. Bennett e J. Gill. Relative to a Random Oracle A, PA 6= NPA 6= coNPA with
Probability 1. SIAM Journal on Computing, 10(1):96113, 1981.
[11] P. Berman. Relationship between density and deterministic complexity of NPcomplete languages. Fifth International Colloquium on Automata, Languages, and
Programming, paginas 6371, 1978.
109
110
REFERENCIAS
BIBLIOGRAFICAS
[12] M. Blum. A machine-independent theory of the complexity of recursive functions.

Journal of the ACM, 14(2):336, 1967.
[13] R.V. Book, T.J. Long, e A.L. Selman. Quantitative relativizations of complexity
classes. SIAM Journal on Computing, 13:461, 1984.
[14] R.B. Boppana, J. H
astad, e S. Zachos. Does co-NP have short interactive proofs?
Information Processing Letters, 25(2):127132, 1987.
[15] R.B. Boppana e M. Sipser. The complexity of finite functions. Handbook of Theoretical Computer Science, 14:757804, 1990.
[16] A. Borodin. Computational complexity and the existence of complexity gaps. Journal of the ACM, 19(1):158174, 1972.
[17] H. Buhrman, L. Fortnow, e T. Thierauf. Nonrelativizing separations. Proceedings
of the Thirteenth Annual IEEE Conference on Computational Complexity, paginas
812, 1998.
[18] J.Y. Cai e H. Zhu. Progress in computational complexity theory. Journal of Computer Science and Technology, 20(6):735750, 2005.
[19] W.A. Carnielli e R.L. Epstein. Computabilidade - Funcoes Computaveis, Logica e
os Fundamentos da Matematica. Editora Unesp, 2006.
[20] A.K. Chandra, D.C. Kozen, e L.J. Stockmeyer. Alternation. Journal of the ACM,
28(1):114133, 1981.
[21] B. Chor, O. Goldreich, e J. Hastad. The random oracle hypothesis is false. Manuscrito, 1990.
[22] A. Cobham. The Intrinsic Computational Difficulty of Functions. Proceedings of
the Third International Congress for Logic, Methodology and Philosophy of Science.
North-Holland Pub. Co., 1965.
[23] P.J. Cohen e M. Davis. Set theory and the continuum hypothesis. Addison-Wesley,
1966.
[24] S. Cook. The importance of the P versus NP question. Journal of the ACM,
50(1):2729, 2003.
[25] S. Cook e P. Nguyen. Logical foundations of proof complexity. Cambridge University
Press, 2010.
REFERENCIAS
BIBLIOGRAFICAS
111
[26] S.A. Cook. The complexity of theorem-proving procedures. Proceedings of the third
annual ACM symposium on Theory of computing, 1971.
[27] S.A. Cook. A hierarchy for nondeterministic time complexity. Journal of Computer
and System Sciences, 7(4):343353, 1973.
[28] Stephen Cook.
The P versus NP problem, 2001. Disponvel em http://www.

claymath.org/prize_problems/p_vs_np.pdf.
[29] T.H. Cormen, C.E. Leiserson, e R.L. Rivest. Introduction to algorithms. The MIT
press, 2001.
[30] S.C. Coutinho. Primalidade em tempo polinomial: uma introducao ao algoritmo
AKS. IMPA, 2003.
[31] Martin Davis. The Undecidable. Raven Press, Hewlett, NY, 1965.
[32] M. Dekhtyar. On the relativization of deterministic and nondeterministic complexity
classes. Mathematical Foundations of Computer Science, paginas 255259, 1976.
[33] D.Z. Du e K.I. Ko. Theory of computational complexity. Wiley New York, 2000.
[34] J. Edmonds. Paths, trees, and flowers.
17(3):449467, 1965.
Canadian Journal of Mathematics,
[35] S. Fenner, L. Fortnow, e S.A. Kurtz. The isomorphism conjecture holds relative to
an oracle. Proceedings of the 33rd Annual Symposium on Foundations of Computer
Science, paginas 3039, 1992.
[36] M.J. Fischer e M.O. Rabin. Super-Exponential Complexity of Presburger Arithmetic, 1974.
[37] L. Fortnow. Two Proofs of Ladners Theorem.
[38] L. Fortnow. The role of relativization in complexity theory. Bulletin of the EATCS,
52:229243, 1994.
[39] L. Fortnow. Diagonalization. Current trends in theoretical computer science. World
Scientific Publishing Company, 2001.
[40] L. Fortnow. Beyond NP: the work and legacy of Larry Stockmeyer. Proceedings of
the thirty-seventh annual ACM symposium on Theory of computing, paginas 120
127. ACM, 2005.
112
REFERENCIAS
BIBLIOGRAFICAS
[41] L. Fortnow. The status of the P versus NP problem. Communications of the ACM,
52(9):7886, 2009.
[42] L. Fortnow e S. Homer. A short history of computational complexity. Bulletin of
the EATCS, 80:95133, 2003.
[43] L. Fortnow e M. Sipser. Are there interactive protocols for co-NP languages? Information processing letters, 28(5):249251, 1988.
[44] R.M. Friedberg. Two recursively enumerable sets of incomparable degrees of unsolvability. Proceedings of the National Academy of Sciences of the United States of
America, 43(2):236238, 1957.
[45] M.R. Garey e D.S. Johnson.
completeness, 1979.
Computers and intractability: a guide to NP-
[46] W.I. Gasarch. The P = NP Poll. Disponvel em http://www.cs.umd.edu/~gasarch/

papers/poll.pdf.
[47] O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge
University Press, 2008.
[48] T. Gowers, J. Barrow-Green, e I. Leader. The Princeton companion to mathematics.
Princeton University Press, 2008.
[49] M. Grohe. Fixed-Point Definability and Polynomial Time on Graphs with Excluded
Minors.
[50] J. Hartmanis e L. Berman. On isomorphisms and density of NP and other complete
sets. Proceedings of the eighth annual ACM symposium on Theory of computing,
paginas 3040. ACM, 1976.
[51] J. Hartmanis, R. Chang, D. Ranjan, e P. Rohatgi. Structural complexity theory:
Recent surprises. SWAT90, paginas 112, 1990.
[52] J. Hartmanis e J.E. Hopcroft. Independence results in computer science. ACM
SIGACT News, 8(4):1324, 1976.
[53] J. Hartmanis, N. Immerman, e V. Sewelson. Sparse sets in NP-P: EXPTIME versus
NEXPTIME. Information and Control, 65(2-3):158181, 1985.
[54] J. Hartmanis e R.E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285306, 1965.
REFERENCIAS
BIBLIOGRAFICAS
113
[55] F.C. Hennie. One-tape, off-line Turing machine computations. Inf. and Control,
8:553578, 1965.
[56] F.C. Hennie e R.E. Stearns. Two-tape simulation of multitape Turing machines.
Journal of the ACM, 13(4):533546, 1966.
[57] M. Hirvensalo. Quantum computing. Natural computing series. Springer Verlag,
2004.
[58] J. Hopcroft, W. Paul, e L. Valiant. On time versus space. Journal of the ACM,
24(2):332337, 1977.
[59] J. E. Hopcroft e J. K. Wong. Linear time algorithm for isomorphism of planar
graphs. STOC 74: Proceedings of the sixth annual ACM symposium on Theory of
computing, paginas 172184, New York, NY, USA, 1974. ACM.
[60] M. Hutter. The Fastest and Shortest Algorithm for All Well-Defined Problems.
International Journal of Foundations of Computer Science, 13(3):431443, 2002.
[61] N. Immerman. Descriptive complexity. Springer Verlag, 1999.
[62] R. Impagliazzo. Computational complexity since 1980. FSTTCS 2005: Foundations
of Software Technology and Theoretical Computer Science, paginas 1947.
[63] D. Joseph e P. Young. Independence results in computer science?
Computer and System Sciences, 23(2):205222, 1981.
Journal of
[64] R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55(1-3):4056, 1982.
[65] R. Kannan. Towards separating nondeterminism from determinism. Theory of
Computing Systems, 17(1):2945, 1984.
[66] R.M. Karp. Reducibility among combinatorial problems. Complexity of Computer
Computations, paginas 85103, 1972.
[67] P. Kaye, R. Laflamme, e M. Mosca. An introduction to quantum computing. Oxford
University Press, USA, 2007.
[68] K.I. Ko. Relativized polynomial time hierarchies having exactly k levels. Proceedings
of the twentieth annual ACM symposium on Theory of computing, paginas 245253.
ACM, 1988.
114
REFERENCIAS
BIBLIOGRAFICAS
[69] D. Kozen. Indexings of subrecursive classes.

11(3):277301, 1980.
Theoretical Computer Science,
[70] S.A. Kurtz. On the random oracle hypothesis. Information and Control, 57(1):40
47, 1983.
[71] S.A. Kurtz, S.R. Mahaney, e J.S. Royer. The isomorphism conjecture fails relative
to a random oracle. Journal of the ACM, 42(2):420, 1995.
[72] S.A. Kurtz, M.J. Odonnell, e J.S. Royer. How to prove representation-independent
independence results. Information Processing Letters, 24(1):510, 1987.
[73] R.E. Ladner. On the structure of polynomial time reducibility. Journal of the ACM,
22(1):155171, 1975.
[74] L.A. Levin. Universal search problems. Problemy Peredachi Informatsii, 9(3):265
266, 1973.
[75] M. Li e P. Vitanyi. An introduction to Kolmogorov complexity and its applications.
Springer-Verlag New York Inc, 2008.
[76] R.J. Lipton e A. Viglas. On the complexity of SAT. 40th Annual Symposium on
Foundations of Computer Science, paginas 459464, 1999.
[77] W. Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape
Turing machines. Proceedings of the sixteenth annual ACM symposium on Theory
of computing. ACM, 1984.
[78] S.R. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and
Hartmanis. Journal of Computer and System Sciences, 25(2):130143, 1982.
[79] A.R. Meyer e L.J. Stockmeyer. The equivalence problem for regular expressions
with squaring requires exponential space. IEEE Conference Record of 13th Annual
Symposium on Switching and Automata Theory, paginas 125129, 1972.
[80] A.R. Meyer e L.J. Stockmeyer. Word problems requiring exponential time. Proc.
5th ACM Symp. on the Theory of Computing, paginas 19, 1973.
[81] G.L. Miller. Riemanns hypothesis and tests for primality. Journal of computer and
system sciences, 13(3):300317, 1976.
[82] A.A. Muchnik. On the unsolvability of the problem of reducibility in the theory of
algorithms. Dokl. Akad. Nauk SSSR, NS, volume 108, 1956.
REFERENCIAS
BIBLIOGRAFICAS
115
[83] A. Nash, R. Impagliazzo, e J. Remmel. Universal languages and the power of

diagonalization. Proc. 18th IEEE Conference on Computational Complexity, paginas
337346, 2003.
[84] P. Odifreddi. Classical Recursion Theory. Elsevier, Amsterdam, 1999.
[85] P. Odifreddi. Classical Recursion Theory. Volume 2. Elsevier, Amsterdam, 1999.
[86] M. Ogiwara e O. Watanabe. On polynomial time bounded truth-table reducibility
of NP sets to sparse sets. Proceedings of the twenty-second annual ACM symposium
on Theory of computing, paginas 457467. ACM, 1990.
[87] I.C. Oliveira e A.V. Moura. A New Look at Some Classical Results in Computational
Complexity. ECCC Electronic Colloquium on Computational Complexity, TR09
025, 2009.
[88] C.H. Papadimitriou. Computational complexity. John Wiley and Sons Ltd., 2003.
[89] W.J. Paul, N. Pippenger, E. Szemeredi, e W.T. Trotter. On determinism versus
non-determinism and related problems. 24th Annual Symposium on Foundations of
Computer Science, paginas 429438, 1983.
[90] A.A. Razborov e S. Rudich. Natural proofs. Proceedings of the twenty-sixth annual
ACM symposium on Theory of computing, paginas 213. ACM, 1994.
[91] K.W. Regan. Understanding the Mulmuley-Sohoni Approach to P vs. NP. Bulletin
of the EATCS, 78:8699, 2002.
[92] O. Reingold. Undirected st-connectivity in log-space. Proceedings of the thirtyseventh annual ACM Symposium on Theory of computing, paginas 385. ACM, 2005.
[93] H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGrawHill, 1967.
[94] W. Rudin e J. Cofman. Principles of mathematical analysis. McGraw-Hill New
York, 1964.
[95] J.E. Savage. Models of computation: Exploring the power of computing. AddisonWesley Publishing Company, Reading, MA, 1998.
[96] M. Schaefer e C. Umans. Completeness in the polynomial-time hierarchy: A compendium. Sigact News, 33(3):3249, 2002.
116
REFERENCIAS
BIBLIOGRAFICAS
[97] U. Schoning. A uniform approach to obtain diagonal sets in complexity classes.

Theoretical Computer Science, 18(1):95103, 1982.
[98] J.I. Seiferas. Machine-Independent Complexity Theory, Handbook of Theoretical
Computer Science (vol. A): Algorithms and Complexity, 1991.
[99] J.I. Seiferas, M.J. Fischer, e A.R. Meyer. Separating nondeterministic time complexity classes. Journal of the ACM, 25(1):146167, 1978.
[100] A. Selman. On the structure of NP. Notices Amer. Math. Soc, 21(6):310, 1974.
[101] A. Shamir. IP = PSPACE. Journal of the ACM, 39(4):869877, 1992.
[102] M. Sipser. The history and status of the P versus NP question. Proceedings of the
twenty-fourth annual ACM symposium on Theory of computing, paginas 603618.
ACM New York, NY, USA, 1992.
[103] M. Sipser. Introduction to the Theory of Computation. PWS, Boston, MA, 1996.
[104] R.E. Stearns, J. Hartmanis, e P.M. Lewis. Hierarchies of memory limited computations. Proceedings of the 6th Annual Symposium on Switching Circuit Theory and
Logical Design, paginas 179190. IEEE Computer Society, 1965.
[105] L.J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science,
3(1):122, 1976.
[106] L. Trevisan. The Program-Enumeration Bottleneck in Average-Case Complexity
Theory. ECCC Electronic Colloquium on Computational Complexity, TR10034,
2010.
[107] A.M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(1):230, 1937.
[108] H. Vollmer e K.W. Wagner. Measure one results in computational complexity theory. Advances in Algorithms, Languages, and Complexity, paginas 285312, 1997.
[109] A. Wigderson. P, NP and Mathematics - A Computational Complexity Perspective.
Proc. of the International Congress of Mathematicians, 2006.
[110] R. Williams. Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity, 17(2):179219, 2008.
[111] R. Williams. Alternation-trading proofs, linear programming, and lower bounds.
STACS, 2010.
REFERENCIAS
BIBLIOGRAFICAS
117
[112] G.J. Woeginger.
The P vs NP Page. Disponvel em http://www.win.tue.nl/

~gwoegi/P-versus-NP.htm.
[113] C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3(1):2333, 1976.
[114] M. Yannakakis. Expressing combinatorial optimization problems by linear programs.
Journal of Computer and System Sciences, 43(3):441466, 1991.
[115] T. Yato e T. Seta. Complexity and completeness of finding another solution and
its application to puzzles. IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences, 86(5):10521060, 2003.
[116] S. Zak. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327
333, 1983.

Artigo Complexidade

Enviado por

Direitos autorais:

Formatos disponíveis

Artigo Complexidade

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Artigo Complexidade

Enviado por

Direitos autorais:

Formatos disponíveis

Complexidade Computacional e o Problema P vs NP

Este exemplar corresponde a` redacao final da

Campinas, 10 de agosto de 2010.

Prof. Dr. Arnaldo Vieira Moura (Orientador)

Dissertacao apresentada ao Instituto de Computacao, unicamp, como requisito parcial para

FICHA CATALOGRFICA ELABORADA PELA

Oliveira, Igor Carboni

Complexidade computacional e o problema P vs NP/Igor Carboni

Ttulo em ingls: Computational complexity and the P vs NP problem.

Complexidade Computacional e o Problema P vs NP

Suporte financeiro da Fundac

formulacoes equivalentes para esse problema, alem de discutirmos sua importancia e os

4.7 Algoritmos Otimos

momento a sua habilidade de computar, de transformar informacao em conhecimento. E

1.2. Computabilidade vs Complexidade

referencia indicada na secao final deste captulo.

A pesquisa em complexidade computacional pode ser dividida em dois grandes grupos.

1.5. Terminologia Basica e Notacao

A notacao e os conceitos basicos utilizados no texto sao usuais em teoria da computacao

w = w1 w2 . . . wk = wk wk1 . . . w1 . O smbolo  detona a palavra vazia. A concatenacao de

um fato surpreendente a existencia de um modelo computacional aparentemente caE

1.6. Maquinas de Turing

leitura de Sipser [103].

cada passo a maquina se encontra em um estado q Q especfico. Existem dois estados

1.6. Maquinas de Turing

atingir o estado qf (desprezamos os infinitos smbolos `a direita da palavra de sada).

Para estudar a dificuldade dos problemas computacionais e preciso quantificar a nocao

1.8. Um Exemplo de Limitante Inferior

facil perceber que a maquina de Turing apresentada na secao anterior computa

Um Exemplo de Limitante Inferior

Considere novamente a linguagem PALIN = {x {0, 1}? : x e um palndromo }. E

1.8. Um Exemplo de Limitante Inferior

isso depende apenas do tamanho da tupla ligada a x e de uma constante cM 0 relacionada

Uma excelente introducao `a teoria da computacao e o livro de Sipser [103]. Para um

1.9. Referencias Adicionais

em relacao a outros modelos computacionais e o desenvolvimento de um computador

A mera existencia de um programa de computador capaz de resolver um problema

Captulo 2. Introducao ao Problema P vs NP

O problema P vs NP procura estabelecer essa questao para todos os problemas com

Captulo 2. Introducao ao Problema P vs NP

A descricao apresentada anteriormente para o problema P vs NP corresponde a` sua

Captulo 2. Introducao ao Problema P vs NP

x L w {0, 1}p(|x|) tal que V (x, w) = 1.

Captulo 2. Introducao ao Problema P vs NP

Nesta secao vamos demonstrar que a versao de busca do problema P vs NP discutida

2.4. Uma Formulacao Alternativa

M imprime um certificado w para x (em relacao ao verificador V ). Em outras palavras,

A classe NP tambem pode ser definida atraves da introducao de um novo recurso

Captulo 2. Introducao ao Problema P vs NP

escolhas nao-determinsticas para aplicacao das funcoes de transicao de M em que o

2.5. Reducoes e Problemas Completos

Ao final da decada de sessenta, uma grande classe de problemas computacionais para os

Captulo 2. Introducao ao Problema P vs NP

Suponha que uma linguagem L1 seja redutvel a uma linguagem L2 . Se resolvemos

2.5. Reducoes e Problemas Completos

Captulo 2. Introducao ao Problema P vs NP

Demonstracao. O fato de que SAT NP e facil de ser provado, pois os certificados

2.6. Importancia Matematica

w = w1 w2 . . . wk = wk wk1 . . . w1 . O smbolo detona a palavra vazia. A concatenacao de