BCC204 - Teoria dos Grafos€¦ · MarcoAntonioM.Carvalho Departamento de Computação Instituto de Ciências Exatas e Biológicas Universidade Federal de Ouro Preto 23desetembrode2019

BCC204 - Teoria dos Grafos

Marco Antonio M. Carvalho

Departamento de ComputaçãoInstituto de Ciências Exatas e Biológicas

Universidade Federal de Ouro Preto

23 de setembro de 2019

Marco Antonio M. Carvalho (UFOP) BCC204 23 de setembro de 2019 1 / 44

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I [email protected]

Para solicitar acesso:I http://groups.google.com/group/bcc204


http://www.decom.ufop.br/marco/

[email protected]

http://groups.google.com/group/bcc204

Conteúdo

1 Problemas Intratáveis

2 P =? NP Poll


Problemas Intratáveis

Aviso!Esta apresentação é uma introdução informal à questão P vs. NP.

Não há a intenção de ser totalmente precisa historicamente e tecnicamente.

Este tópico será estudado com profundidade em diferentes disciplinas do curso degraduação.

Baseado no artigo “The Status of the P Versus NP Problem”.



Edsger Dijkstra,Prêmio Turing em 1972“Ciência da computação tem tanto a ver com ocomputador como a Astronomia com o telescópio, aBiologia com o microscópio, ou a Química com os tubosde ensaio. A Ciência não estuda ferramentas, mas o quefazemos e o que descobrimos com elas.”



IntroduçãoQuase todos algoritmos vistos até aqui possuem tempo polinomial: em entradas detamanho n, o tempo de execução no pior caso é O(nk), para alguma constante k .

Podemos pensar, intuitivamente, que todos os problemas podem ser resolvidos emtempo polinomial.

Entretanto, a resposta é não. Há problemas que não podem ser resolvidos pelocomputador, e outros que podem, porém, não em tempo O(nk), para algumaconstante k .

Geralmente, designamos os problemas resolvíveis em tempo polinomial comotratáveis, ou fáceis.

Por outro lado, designamos os problemas resolvíveis apenas em tempo suprapolinomial como intratáveis, ou difíceis.



IntroduçãoUm problema é considerado indecidível caso não seja possível criar um algoritmoqualquer para sua solução, e. g., o Problema da Parada:

“Dadas uma descrição de um programa e uma entrada finita, decida se o programatermina de rodar ou rodará indefinidamente, dada essa entrada.”

Um problema é considerado intratável caso não haja algoritmo em tempopolinomial que o resolva deterministicamente.

Veremos alguns exemplos mais à frente.



Alan TuringI Matemático, lógico e criptoanalista inglês

I Participação importante na II Guerra Mundial.I Pai da Ciência da Computação

I Dedicou a via à teoria da computabilidade.

I Formalizou os conceitos de algoritmo ecomputabilidade.

I Aos 24 anos, criou a Máquina de Turing.I Parte de sua vida foi retratada no filme “O Jogo da

Imitação” de 2014.I Hoje o Prêmio Turing equivale ao Nobel da

Computação.



Máquina de TuringA Máquina de Turing é um modelo de computador conceitual, abstrato, tambémchamada de Máquina Universal.

Realiza qualquer computação matemática que possa ser representada por umalgoritmo.

Capaz de computar tudo que é computável.

É o centro do conceito da arquitetura dos computadores modernos.



Máquina de Turing vs. ENIACA primeira referência a uma máquina de Turing éde um artigo publicado em em 1936.

O ENIAC foi o primeiro computador eletrônico depropósitos variados – anunciado em 1946.



Máquina de TuringExistem basicamente dois tipos de Máquinas deTuring:I Máquina de Turing Determinística:

I Se ’A’, então faça ’B’.I Máquina de Turing Não Determinística:

I Se ’A’, então faça ’B’ ou ’C’ ou ’D’ ou ...



ComputabilidadeAlan Turing, aos 24 anos, delineou a idéia de computabilidade.

Existe alguma coisa que não possa ser feita mecanicamente (ou seja, sem intuiçãoou inteligência)?

Em seu artigo original, Turing demonstra a existência de um problemainsolucionável mecanicamente.



ComputabilidadeA Computabilidade e a Teoria da Complexidade Computacional estudam os limitesda computação:I Quais problemas jamais poderão ser resolvidos por um computador,

independente da sua velocidade ou memória?I 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çãoimpraticável?



Petaflops = 1 quadrilhão de flops

O Computador Mais Potente do MundoI Department of Energy (DOE) Oak Ridge

National Laboratory(ORNL);I Desde junho de 2018;I Performance de 143.5 Petaflops por segundo -

quase 1.4x o segundo colocado;I US$325 milhões;I 9216 CPUS de 22 cores; 27.649 NVIDIA Tesla

V100 GPUs;I Sistema Operacional Red Hat Enterprise Linux;I Memória: 250.000.000 GB;

I Propósito: pesquisa, como cosmologia, medicinae climatologia.



O Computador Mais Potente do MundoO IBM Summit é capaz de realizar ≈ 12,23×1016 = 1.223.000.000.000.000.000 operaçõesbásicas por segundo



PSuponhamos que temos um grande grupo de alunos e precisamos agrupá-los emduplas compatíveis para um trabalho:I Nem todos os alunos são compatíveis entre si;I Tentar todas as possibilidades não é uma alternativa;I Se o grupo tiver 40 alunos, temos mais do que 300 bilhões de trilhões de

possíveis pares.Em 1965, Jack Edmonds criou um algoritmo eficiente para resolver este problemae ajudou a definir o que é computação eficiente.



PComputação eficiente passou a ser definida como a existência de um algoritmo queresolve um problema em tempo polinomial em relação ao tamanho da entrada.

A classe de problemas para os quais há algoritmos eficientes passou a serconhecida como classe P, de “Tempo Determinístico Polinomial”.



NPInfelizmente, para muitos problemas parece não haver algoritmo eficiente:I E se quisermos achar o maior grupo de alunos tal que todos são compatíveis

entre si (clique máximo)?I E se quisermos sentar à mesa todos os alunos, de maneira que dois alunos

incompatíveis não fiquem lado a lado (ciclo hamiltoniano)?I E se quisermos dividir os alunos em trios, de forma que cada aluno estará

sempre com outros dois incompatíveis (3 coloração)?



NPTodos estes problemas possuem uma propriedade em comum:I Dada uma solução qualquer (por exemplo, o mapa das cadeiras em uma

mesa), é possível conferir a solução de maneira eficiente.

É como um quebra cabeça: verificar se está montado é mais fácil do que montar.

O conjunto de problemas que possuem soluções verificáveis em tempo polinomialdefine a classe NPI De “Tempo Polinomial Não Determinístico”.I Somente uma Máquina de Turing Não Determinística pode resolvê-lo em

tempo determinístico polinomial.



NP-CompletoOs mais difíceis problemas em NP formam ainda uma outra classe, a NP-Completo.

A característica notória desta classe é que um algoritmo eficiente para qualquer umdos problemas pode ser adaptado facilmente para qualquer outro problema destaclasse.

Resolver um implica em resolver todos.

Vários problemas NP-completos são interessantes porque se parecem muito comproblemas fáceis:I Caminho mais curto vs. Caminho mais longo;I Ciclo Euleriano vs. Ciclo Hamiltoniano;I 2-SAT vs. 3-SAT.



NP-CompletoEm 1971, Richard Karp identificou os primeiros 21problemas da classe e contribuiu para o desenvolvimentoda teoria da NP-Completude.

Posteriormente, centenas de outros problemas foramidentificados por outros pesquisadores.



NP-CompletoA maioria dos problemas de interesse pertencem comprovadamente à classeNP-Completo:I Determinar a sequência de DNA que melhor se assemelha a um fragmento de

DNA;I Determinar procedimentos eficientes para predição de estrutura de proteínas;I Determinar se uma afirmação matemática possui uma prova curta;I Etc...



P vs. NPA partir destas descobertas, grande parte dos cientistas da computação passou aacreditar que P6=NP.

Provar isto se tornou a questão mais importante da ciência da computação e umadas mais importantes da matemática.





P vs. NP – Um dos Problemas do MilênioO Clay Mathematics Institute elencou 7 problemas matemáticos e oferece um prêmio deum 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 2000a:

I P vs. NP;I A conjectura de Poincaré (resolvido por Grigori Perelman em 2006);I A conjectura de Hodge;I A hipótese de Riemann;I A existência de Yang-Mills e a falha na massa;I A existência e suavidade de Navier-Stokes;I A conjectura de Birch e Swinnerton-Dyer.

aVeja uma descrição informal em http://goo.gl/wdWzzH


http://goo.gl/wdWzzH


E Se P = NP?“O que ganharíamos com P=NP faria com que a Internet inteira parecesse apenasum rodapé na história’.’– Fortnow, L. 2009



E Se P = NP?Várias tarefas se tornariam triviais:I Transporte de pessoas e produtos mais rápido e mais barato;I Indústrias produzindo mais rápido e mais barato;I Traduções automáticas;I Reconhecimento de visão;I Compreensão de linguagens;I Previsão do tempo, terremotos e tsunamis;I Provas curtas para teoremas matemáticos



E Se P = NP?Adeus criptografia!

A criptografia se baseia em problemas difíceis de serem resolvidos, como afatoraçã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 umproblema trivial...



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 parapesquisas futuras.

Se soubermos que um problema é intratável, não tentaremos resolvê-lo de maneiraeficiente, ao invés disso, tentaremos soluções aproximadas ou parciais, comtécnicas apropriadas.

Podemos utilizar a dificuldade em resolver problemas a nosso favor – como nacriptografia.



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 problemasindustriais, matemáticos, computacionais, etc..

Aparecem aí a Otimização Combinatória e a Pesquisa Operacional.



P vs. NP AtualmenteExistem 116 provas sobre P vs. NP, registradas pelo P vs. NP Page.

Em 2016 tivemos seis tentativas (igual:4, diferente:2).

De 26 de setembro de 2016 em diante, nenhuma atualização.



Prof. Sóstenes Luiz Soares Lins (UFPE)“Este trabalho permanece não publicado: continuopesquisando que problemas de decisão são a eleredutíveis. No período 2008-2010, provei que MAX-CUTera um tal problema. Isto implicaria P=NP. Escrevi 52versões da prova do resultado até descobrir, um erro em10/01/2010.”

“Numa época de ciência descartável (focada em númerode publicações e estatísticas estranhas, dissociadas doconteúdo), orgulho-me de não transigir e ao menos tentardescobrir algo perene e importante.”


P =? NP Poll

P vs. NP AtualmenteUm artigo de 2002 realizou uma pesquisa/entrevista com 100 dos maiores teóricosda computação do mundo.

Dez anos depois, a pesquisa/entrevista foi refeita, desta vez,com 152 dos maioresteóricos da computação do mundo.

Os números entre parênteses indicam o percentual de respostas nas duas ediçõesda pesquisa.


P =? NP Poll

P vs. NP Atualmente

O que você acha de P vs. NP?

I P=NP (9% – 9%);I P!=NP(61% – 83%);I Não sei (22% – 0,6%);I Não me importo (1% – 3%);I Independe(4% – 3%).


P =? NP Poll

P vs. NP Atualmente

Quando solucionaremos P vs. NP?

I 2010-2019 (12% – 0,01%);I 2020-2029 (13% – 11%);I 2030-2039 (10% – 12%);I 4000-4100 (0% – 2%);I Daqui há muito tempo (0% – 14%);I Antes de 2100 (62% – 53%);I Depois de 2100 (17% – 41%);I Nunca (5% – 3%).


P =? NP Poll

P vs. NP Atualmente

Qual será o método utilizado na prova?

I Novas técnicas (65 pessoas);I Técnicas conhecidas (5 pessoas);I Um algoritmo (6 pessoas);I Milagre (1 pessoa);I “Não saberemos até que seja resolvido”;I “Não vou te dizer”;I “Os aliens nos dirão”;I ”Livros já amarelados, incluindo aqueles que sequer foram escritos ainda”.


P =? NP Poll

Scott Aaronson, MIT“I believe P 6= NP on basically the same grounds that Ithink I won’t be devoured tomorrow by a 500-foot-tallrobotic marmoset from Venus, despite my lack of proof inboth cases.”


P =? NP Poll

Stephen Cook, Universidade de Toronto“P 6= NP will not be resolved in the next 20 years and willneed new techniques”.


P =? NP Poll

Lance Fortnow, Georgia Tech“P 6=NP. It will be resolved in an unpredictably long time.If I knew what kinds of techniques would be used Iwouldn’t tell.”


P =? NP Poll

Richard Karp“I believe intuitively P 6= NP but it is only an intuition.”


P =? NP Poll

Michael Sipser, MIT“As far as I know, not much has changed mathematicallyrelevant to P vs. NP since 2002 so I have nothing to addto my previous response to your questionnaire.

Use my prior response; however, update it so that I predictit will be solved 25 years from now, not from 2002.’

(...) And I’ll stick with my earlier prediction that theresolution will be a proof that P 6= NP.”



Conclusão”(...) my first reaction was the article could be written in two words: Still open.” -Fortnow, L. 2009



ReferênciasI Clay Mathematics Institute. The Millenium Problems. Disponível em:

http://www.claymath.org/millennium/P_vs_NP/. Acessado em 20 de setembro de2019.

I Fortnow, L. 2009. The Status of the P Versus NP Problem. Communications of the ACM,Vol. 52 No. 9, Pages 78-86.

I Gasarch, W. I., 2012. Guest Column: The Second P =? NP Poll. ACM SIGACT news.I The P vs. NP Page. Disponível em:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm. Acessado em 20 de setembro de2019.

I Top 500 Supercomputer Sites. Disponível em: http://www.top500.org/lists/.Acessado em 20 de setembro de 2019.

I Turing, A. On computable numbers, with an application to the Etscheidungs problem.Proceedings of the London Mathematical Society 42 (1936), 230-265.


http://www.claymath.org/millennium/P_vs_NP/

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

http://www.top500.org/lists/

Dúvidas?


Documents

BCC204 - Teoria dos Grafos€¦ · MarcoAntonioM.Carvalho Departamento de Computação Instituto de Ciências Exatas e Biológicas Universidade Federal de Ouro Preto 23desetembrode2019