091 aula 09 N versus NP

Prévia do material em texto

P vs. NP: Uma introdução 
 
 
Prof. Marco Antonio M. Carvalho 
Quem Sou Eu? 
!  Bacharel em Ciência da Computação (2005) – Faculdades 
Integradas de Caratinga 
!  Mestre em Engenharia Eletrônica e Computação (2008) – ITA 
!  Doutor em Engenharia Eletrônica e Computação (2013) – ITA 
!  Interesses: 
!  Teoria da Computação, Otimização Combinatória, Pesquisa Operacional; 
!  Análise de Risco; 
!  Maratona de Programação. 
!  Professor do DECOM/UFOP desde 2010/2 
!  Disciplinas de programação; 
!  Maratona de Programação; 
!  Membro do GOAL-UFOP. 
2 
Contato 
! marco.opt@gmail.com 
! 3559-1663 
! Sala COM45 – DECOM/ICEB III 
3 
Aviso! 
! Esta apresentação é uma introdução informal ao 
problema P vs. NP; 
! Não há a intenção de ser totalmente preciso 
historicamente e tecnicamente; 
! Este tópico será estudado com profundidade em 
diferentes disciplinas do curso de graduação; 
! Baseado no artigo “The Status of the P Versus NP 
Problem”. 
4 
5 
"Ciência da computação tem 
tanto a ver com o computador 
como a Astronomia com o 
telescópio, a Biologia com o 
microscópio, ou a Química com os 
tubos de ensaio. A Ciência não 
estuda ferramentas, mas o que 
fazemos e o que descobrimos com 
elas." 
Edsger Dijkstra (1930-2002) 
Prêmio Turing em 1972 
Alan Turing 
6 
Alan Turing 
7 
!  Matemático, lógico e criptoanalista inglês 
!  Participação importante na II Guerra Mundial. 
!  Pai da Ciência da Computação 
!  Dedicou a via à teoria da computabilidade; 
!  Formalizou os conceitos de algoritmo e 
computabilidade; 
!  Aos 24 anos, criou a Máquina de Turing. 
!  Parte de sua vida foi retratada no filme 
Breaking the Code de 1996. 
!  Hoje o Prêmio Turing equivale ao Nobel da 
Computação. 
Alan Turing (1912-1954) 
Máquina de Turing 
! A Máquina de Turing é um modelo de computador 
conceitual, abstrato, também chamada de 
Máquina Universal 
!  Realiza qualquer computação matemática que possa ser 
representada por um algoritmo; 
!  Capaz de computar tudo que é computável; 
!  É o centro do conceito da arquitetura dos computadores 
modernos. 
8 
Máquina de Turing vs. ENIAC 
! A primeira referência a uma 
máquina de Turing é de um 
artigo publicado em em 1936; 
! O ENIAC foi o primeiro 
computador eletrônico de 
propósitos variados 
!  Anunciado em 1946. 
9 
ENIAC (1946) 
Máquina de Turing 
!  Existem basicamente dois tipos de 
Máquinas de Turing: 
!  Máquina de Turing Determinística: 
!  Se ‘A’, então faça ‘B’. 
!  Máquina de Turing Não 
Determinística: 
!  Se ‘A’, então faça ‘B’ ou ‘C’ ou 
‘D’ ou ... 
10 
Máquina de Turing 
Computabilidade 
11 
Computabilidade 
! Alan Turing, aos 24 anos, delineou a idéia de 
computabilidade 
!  Existe alguma coisa que não possa ser feita 
mecanicamente (ou seja, sem intuição ou inteligência)? 
! Utilizamos o conceito de problema computacional 
!  Uma tarefa que deve ser realizada e resulta em uma 
solução. 
! A computabilidade de um problema é intimamente 
relacionada à existência de um algoritmo que o 
resolva. 
12 
Computabilidade 
! As Máquinas de Turing desempenham um papel 
fundamental na computabilidade 
!  Um problema é solúvel se há uma Máquina de Turing para 
aquele problema; 
!  Em seu artigo original, Turing demonstra a existência de um 
problema insolúvel. 
13 
Computabilidade 
!  A Computabilidade e a Teoria da Complexidade 
Computacional estudam os limites da computação: 
1.  Quais problemas jamais poderão ser resolvidos por um 
computador, independente da sua velocidade ou memória? 
2.  Quais problemas podem ser resolvidos por um computador, 
mas requerem um período tão extenso de tempo para 
completar a ponto de tornar a solução impraticável? 
3.  Em que situações pode ser mais difícil resolver um problema 
do que verificar cada uma das soluções manualmente? 
14 
O Problema da Parada 
“Dadas uma descrição de um programa e uma 
entrada finita, decida se o programa termina de rodar 
ou rodará indefinidamente, dada essa entrada.” 
15 
3-SAT 
16 
Instância 3-SAT (x�x�y) � (¬x�¬y�¬y) � (¬x�y�y) 
reduzida ao problema de clique 
O Computador Mais Potente do 
Mundo 
17 
!  China National University of Defense 
Technology; 
!  Junho de 2013; 
!  Performance de 33,86 Petaflops por segundo; 
!  Processadores Intel Xeon E5, Xeon Phi 
!  3.120.000 cores 
!  Sistema Operacional Kylin Linux; 
!  Memória: 1.375 TiB; 
!  Armazenamento: 12,4 PB; 
!  Preço: US$ 390 milhões; 
!  Propósito: pesquisa e educação. 
Tianhe-2 (China) 
O Computador Mais Potente do 
Mundo 
! O Tianhe-2 é capaz de realizar ≈ 3,386 x 1013 = 
33.860.000.000.000.000 operações básicas por 
segundo; 
!  10! = 3628800 ou 3,628800 x 106; 
!  100! = 9,332622 x 10157; 
!  150! = 5,713384 x 10262; 
!  175! = infinito... 
!  1000! = ??? 
18 
Taxa de Crescimento de Funções 
19 
O Paradoxo de Hilbert 
! Considere um hotel hipotético, com um número 
infinito e contável de quartos, todos ocupados; 
!  Intuitivamente, pensamos que o hotel não tem 
capacidade para acomodar novos hóspedes, 
como seria no caso de um hotel com um número 
finito de quartos; 
! Existem diferentes métodos que mostram que o 
hotel pode comportar um número infinito de novos 
hóspedes. 
20 
Computabilidade 
! Das três perguntas anteriores, a última é referente às 
classes de problemas 
!  As mais estudadas são P e NP; 
!  O relacionamento entre as duas é um dos problemas do 
milênio e considerado por alguns como o “elo perdido” da 
ciência da computação; 
!  Surge a teoria da NP-Completude. 
21 
Computabilidade 
! À medida em que resolvemos problemas maiores e 
mais complexos, com auxílio de maior poder 
computacional e algoritmos melhores, os problemas 
intratáveis se destacam; 
! A Teoria da Complexidade Computacional nos 
ajuda a compreender estas limitações 
!  Deixa de ser uma questão teórica da computação para ser 
um princípio básico que permeia todas as ciências. 
22 
P 
23 
P 
! Suponham que temos um grande grupo de alunos 
e precisamos agrupá-los em dupla para um 
trabalho 
!  Nem todos os alunos são compatíveis entre si; 
!  Tentar todas as possibilidades não é uma alternativa; 
!  Se o grupo tiver 40 alunos, temos mais do que 300 milhões 
de trilhões de possíveis pares. 
! Em 1965, Jack Edmonds criou um algoritmo 
eficiente para resolver este problema e ajudou a 
definir o que é computação eficiente 
24 
P 
! Computação eficiente passou a ser definida como 
a existência de um algoritmo que resolve um 
problema em tempo polinomial em relação ao 
tamanho da entrada; 
! A classe de problemas para os quais há algoritmos 
eficientes passou a ser conhecida como classe P 
!  De “Tempo Determinístico Polinomial”. 
25 
NP 
26 
NP 
!  Infelizmente, para muitos problemas parece não haver 
algoritmo eficiente: 
!  E se quisermos dividir os alunos em trios nos quais todos os 
pares de alunos são compatíveis (partição em triângulos)? 
!  E se quisermos achar o maior grupo de alunos tal que todos 
são compatíveis entre si (clique máximo)? 
!  E se quisermos sentar à mesa todos os alunos, de maneira que 
dois alunos incompatíveis não fiquem lado a lado (ciclo 
hamiltoniano)? 
!  E se quisermos dividir os alunos em trios, de forma que cada 
alunos estará sempre com outros dois incompatíveis (3 
coloração)? 
27 
NP 
! Todos estes problemas possuem uma propriedade 
em comum: 
!  Dada uma solução qualquer (por exemplo, o mapa das 
cadeiras em uma mesa), é possível conferir a solução de 
maneira eficiente. 
! O conjunto de problemas que possuem soluçõesverificáveis em tempo polinomial define a classe NP 
!  De “Tempo Polinomial Não Determinístico”; 
!  Somente uma Máquina de Turing Não Determinística pode 
resolvê-lo. 
28 
NP-Completo 
29 
NP-Completo 
! Os mais difíceis problemas em NP formam ainda 
uma outra classe, a NP-Completo 
!  Por exemplo, Partição em Triângulos, Clique Máximo, Ciclo 
Hamiltoniano e 3-coloração. 
! A característica notória desta classe é que um 
algoritmo eficiente para qualquer um dos 
problemas pode ser adaptado facilmente para 
qualquer outro problema desta classe 
!  Resolver um implica em resolver todos. 
30 
NP-Completo 
! Em 1971, Richard Karp identificou os 
primeiros 21 problemas da classe e 
contribuiu para o desenvolvimento 
da teoria da NP-Completude; 
! Posteriormente, centenas de outros 
problemas foram identificados por 
outros pesquisadores. 
31 
Richard Karp 
! A maioria dos problemas de interesse pertencem 
comprovadamente à classe NP-Completo: 
!  Determinar a sequência de DNA que melhor se assemelha 
a um fragmento de DNA; 
!  Determinar procedimentos eficientes para predição de 
estrutura de proteínas; 
!  Determinar se uma afirmação matemática possui uma 
prova curta; 
!  Etc... 
32 
P vs. NP 
33 
P vs. NP 
! A partir destas descobertas, grande parte dos 
cientistas da computação passou a acreditar que 
P≠NP 
!  Provar isto se tornou a questão mais importante da ciência 
da computação e uma das mais importantes da 
matemática. 
34 
35 
P vs. NP 
!  O Clay Mathematics Institute elencou 7 problemas 
matemáticos e oferece um prêmio de um milhão de dólares 
para quem resolver um deles; 
!  Provar que P=NP ou P!=NP é um dos 7 Problemas do Milênio 
desde o ano 2000. 
!  P versus NP; 
!  A conjectura de Hodge; 
!  A conjectura de Poincaré (resolvido por Grigori Perelman em 2006); 
!  A hipótese de Riemann; 
!  A existência de Yang-Mills e a falha na massa; 
!  A existência e suavidade de Navier-Stokes; 
!  A conjectura de Birch e Swinnerton-Dyer. 
36 Grigori Perelman 
E Se P = NP? 
37 
38 
The Simpsons, Treehouse of Horror VI, 1995. 
E Se P = NP? 
“O que ganharíamos com P=NP faria com que a 
Internet inteira parecer apenas um rodapé na história” 
- Fortnow, L. 2009 
39 
E Se P = NP? 
! Várias tarefas se tornariam triviais: 
!  Transporte de pessoas e produtos mais rápido e mais 
barato; 
!  Indústrias produzindo mais rápido e mais barato; 
!  Traduções automáticas; 
!  Reconhecimento de visão; 
!  Compreensão de linguagens; 
!  Previsão do tempo, terremotos e tsunamis; 
!  Provas curtas para teoremas matemáticos 
!  6 milhões de dólares ao invés de 1 ! 
40 
E Se P = NP? 
! Adeus criptografia! 
!  A criptografia se baseia em problemas difíceis de serem 
resolvidos, como a fatoração de números muito grandes 
em números primos; 
!  Portanto, é impossível de quebrar, a não ser que P=NP e 
fatoração seja um problema trivial... 
41 
O Filme 
!  O filme “Travelling Salesmen”, de 2012, 
conta a história de quatro matemáticos 
que descobrem um algoritmo eficiente 
para o Problema do Caixeiro Viajante, 
um problema NP-Completo 
!  Quando se deparam com as implicações 
globais da descoberta; 
!  O departamento de defesa americano 
oferece US$10 milhões para cada pelo 
algoritmo; 
!  Um dos matemáticos se recusa, sendo 
forçado a revelar um segredo importante 
sobre sua parte do algoritmo. 
42 
E Se P != NP? 
43 
E Se P != NP? 
! Se for provado que P!=NP, não teremos os 
benefícios computacionais de P=NP 
!  Porém, ainda assim teríamos avanços na teoria da 
computação e uma direção para pesquisas futuras; 
!  Se soubermos que um problema é intratável, não 
tentaremos resolvê-lo de maneira eficiente, ao invés disso, 
tentaremos soluções aproximadas ou parciais 
!  Com técnicas apropriadas. 
!  Podemos utilizar a dificuldade em resolver problemas a 
nosso favor 
!  Como na criptografia. 
44 
E Se P != NP? 
! Como dito anteriormente, os problemas de 
interesse são NP-Completos 
!  Ainda precisamos tentar resolvê-los, mesmo sem os 
benefícios de P=NP; 
!  Mesmo não sendo totalmente eficientes, existem “bons” 
algoritmos para problemas industriais, matemáticos, 
computacionais, etc. 
!  Aparecem aí a Otimização Combinatória e a Pesquisa 
Operacional. 
45 
P vs. NP Atualmente 
46 
P vs. NP Atualmente 
! Existem 99 provas sobre P vs. NP, registradas pelo P 
vs. NP Page; 
! Em 2013 tivemos duas tentativas de provas 
!  Em janeiro, Dmitriy Nuriyev; 
!  Em outubro, Frederic Gillet. 
! Nenhuma das provas foi confirmada ainda. 
47 
P vs. NP Atualmente 
48 
!  Prof. Sóstenes Luiz Soares Lins (UFPE) 
!  “Este trabalho permanece não publicado: 
continuo pesquisando que problemas de decisão 
são a ele redutíveis. No período 2008-2010, provei 
que MAX-CUT era um tal problema. Isto implicaria 
P=NP. Escrevi 52 versões da prova do resultado até 
descobrir, um erro em 10/01/2010.” 
!  “Numa época de ciência descartável (focada em 
número de publicações e estatísticas estranhas, 
dissociadas do conteúdo), orgulho-me de não 
transigir e ao menos tentar descobrir algo perene 
e importante.” 
P vs. NP Atualmente 
! Um artigo de 2012 realizou uma pesquisa/entrevista 
com 152 dos maiores teóricos da computação do 
mundo 
!  O que você acha de P vs. NP? 
!  P=NP (9%); 
!  P!=NP(83%); 
!  Não sei (0,6%); 
!  Não me importo (3%); 
!  Independe(3%). 
49 
P vs. NP Atualmente 
!  Quando solucionaremos P vs. NP? 
!  2020-2029 (11%); 
!  2030-2039 (12%); 
!  Daqui há muito tempo (14%); 
!  Antes de 2100 (53%); 
!  Depois de 2100 (41%); 
!  Nunca (3%). 
50 
P vs. NP Atualmente 
!  Qual será o método utilizado na prova? 
!  Novas técnicas (35%); 
!  Um algoritmo (0,04%); 
!  Milagre (1 pessoa); 
!  “Livros já amarelados, incluindo aqueles que sequer foram 
escritos ainda”. 
51 
Conclusão 
52 
Conclusão 
“(...) my first reaction was the article could be written 
in two words: Still open.” 
- Fortnow, L. 2009 
53 
54 
Perguntas? 
Referências 
!  Clay Mathematics Institute. The Millenium Problems. Disponível em: http://
www.claymath.org/millennium/P_vs_NP/. Acessado em 15 de Outubro de 2013. 
!  Fortnow, L. 2009. The Status of the P Versus NP Problem. Communications of the 
ACM, Vol. 52 No. 9, Pages 78-86. 
!  Gasarch, W. I., 2012. Guest Column: The Second P =? NP Poll. ACM SIGACT news. 
!  The P vs. NP Page. Disponível em: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm. 
Acessado em 15 de Outubro de 2013. 
!  Top 500 Supercomputer Sites. Disponível em: http://www.top500.org/lists/2013/06/. 
Acessado em 15 de Outubro de 2013. 
!  Turing, A. On computable numbers, with an application to the Etscheidungs 
problem. Proceedings of the London Mathematical Society 42 (1936), 230–265. 
55