NP-Completude: Demonstração e Aplicações do Problema da Maior Subsequência Comum (LCS)

Exercícios 1 Escolha um problema da lista indicada e faça a demonstração de que esse problema é NPCompleto Cada aluno deve escolher apenas um problema e preencher a planilha indicando a alocação do problema A apresentação deve seguir o método para provar que um problema A é NPCompleto a Defina e apresente exemplos do problema b Apresente aplicações para o problema c Opcional Técnicas computacionais que podem tratar o problema d Prove que o problema pertence a NP e Selecione um problema B que é conhecido como NPCompleto f Descreva um algoritmo que calcule uma função f que mapeia uma entrada do problema B para entrada do problema A g Prove que a função f executa em tempo polinomial h Conclua que o problema é NPCompleto e indique as consequências disso Partition problem 1planarity 3dimensional matching Graph homomorphism Graph partition Longest common subsequence problem Stringtostring correction problem Minimum degree spanning tree Max cut Maximum independent set Minimum kcut Atividade NPCompletude Longest Common Subsequence Problem a Uma sequência pode ser compreendida como o encadeamento ordenado de objetos naturais representados por símbolos comumente caracteres alfanuméricos Uma subsequência consiste em uma sequência contida em uma sequência maior e pode ser obtida extraindose zero ou mais caracteres da sequência original mantendo seu ordenamento Definese subsequência comum a duas ou mais sequências como uma sequência que é subsequência de todas as sequências PAOLI 2016 O problema da Maior Subsequência Comum LCS Longest Common Subsequence consiste em dado sequências determinar a maior 𝑛 2 𝑆1 𝑆2 𝑆𝑛 subsequência de comum as sequências 𝑛 Um instância do problema pode ser obtida considerando 𝑛 3 𝑆1 𝐴𝑆𝑇𝐴 e A maior subsequência comum a estas três 𝑆2 𝑃𝐴𝑁𝑃𝑆𝑃𝐴 𝑆3 𝑁𝐴𝑃𝑃𝑆𝐴𝑇 subsequências é 𝐴𝑆𝐴 b O problema possui aplicações na área de biologia molecular onde é utilizado para comparação de sequências de DNA e no mapeamento de proteínas Também possui em ambientes que visam fazer correção ortográfica ou versionamento de arquivos PEVIANI 2009 c O problema possui solução polinomial quando onde é possível aplicar 𝑛 2 a técnica de Programação Dinâmica Para caso o problema pode ser resolvido por uma abordagem mas de 𝑛 2 tempo exponencial Considere os tamanhos das n sequências 𝑘1 𝑘2 𝑘𝑛 Selecione a sequência de menor tamanho ou seja para todo 𝑆𝑖 𝑘𝑖 𝑘𝑗 𝑗 1 𝑛 Gere todas as subsequências de 2 𝑘𝑖 𝑆𝑖 Para toda subsequência de verifique se também é subsequência de para 𝑆𝑖 𝑆𝑗 todo custo 𝑗 1 𝑛 𝑂𝑘𝑖 Selecione a maior das subsequências comuns as 𝑛 sequências Logo a complexidade desta abordagem é de Este 𝑂2 𝑚𝑖𝑛1 𝑖 𝑛𝑘𝑖 𝑖1 𝑛 𝑘𝑖 algoritmo pode ser eficiente se tivermos sempre a garantia que sempre existirá uma subsequência pequena No caso geral o algoritmo é pouco eficiente Abordagens heurísticas e metaheurísticas são utilizadas quando se deseja obter uma boa solução em tempo não proibitivo porém abrindo mão da garantia da otimalidade d Problema de decisão associado dado sequências e um inteiro 𝑛 2 𝑆1 𝑆2 𝑆𝑛 verifica se existe uma subsequência comum as sequências de tamanho pelo 𝑚 𝑛 menos 𝑚 Precisamos provar que dado uma instância e uma possível solução do problema de decisão associado é possível construir um verificador em tempo polinomial Dado e uma possível solução faça o seguinte 𝑆1 𝑆2 𝑆𝑛 𝑚 𝑆 procedimento PASSO 1 Verifique se 𝑆 𝑚 PASSO 2 Para todo verifique se é uma subsequência 𝑖 1 𝑛 𝑆 de 𝑆𝑖 Percorra as sequência e da esquerda para direita 𝑆𝑖 𝑆 Verifique se o símbolo coincide com o símbolo observado na sequência Caso afirmativo percorra um símbolo da 𝑆 sequência Caso contrário continue com o mesmo 𝑆 símbolo Ao final de cada iteração percorra um símbolo de 𝑆𝑖 Se ao final das iterações for percorrido completamente 𝑆 significa que é subsequência de 𝑆 𝑆𝑖 PASSO 3 Se é subsequência de todo com então 𝑆 𝑆𝑖 𝑖 1 𝑛 é uma subsequência comum as sequências 𝑆 𝑛 O procedimento acima é um procedimento verificador Os passos 1 e 3 podem ser realizado em tempo constante Já o passo 2 tem um custo 𝑂1 onde é o tamanho 𝑂𝑆 𝑖1 𝑛 𝑘𝑖 𝑂𝑚𝑖𝑛1𝑖𝑛𝑘𝑖 𝑛 𝑚𝑎𝑥1𝑖𝑛𝑘𝑖 𝑂𝑛𝑝² 𝑝 da maior sequência Desta forma o procedimento total tem custo ou seja 𝑂𝑛𝑝² tem custo polinomial Portanto 𝐿𝐶𝑆 𝑁𝑃 e O problema selecionado foi o Problema da Cobertura de Vértices VCP Vertex Cover Problem Uma cobertura de vértices de um grafo não orientado é um subconjunto tal que então ou 𝐺 𝑉 𝐸 𝑉 𝑉 𝑢 𝑣 𝐸 𝑢 𝑉 𝑣 𝑉 ou ambos Isto é cada vértice cobre suas arestas incidentes e uma cobertura de vértices para é um conjunto de vértices que cobre todas as arestas em O 𝐺 𝐸 problema da cobertura de vértices visa determine o menor conjunto de vértices que é uma cobertura de vértices do grafo CORMEN 2002 𝐺 Problema da decisão associado Dado um grafo não orientado e um 𝐺 𝑉 𝐸 inteiro verifica se existe uma cobertura de vértices do grafo de tamanho no 𝑡 𝐺 máximo 𝑡 f Abaixo é descrito o procedimento que mapeia uma entrada do Problema de Cobertura de Conjuntos em uma entrada do Problema da Maior Subsequência Comum Dado um grafo não orientado e um inteiro Queremos 𝐺 𝑉 𝐸 𝑘 determinar se existe uma cobertura de vértices do grafo G de tamanho no máximo t Vamos considerar que não possui vértices isolados 𝐺 Considere uma ordenação do conjunto de vértices 𝑉 𝑣1 𝑣2 𝑣𝑛 PASSO 1 Para toda aresta cria a sequência 𝑣𝑖 𝑣𝑗 𝑣1 𝑣𝑖1 𝑣𝑖1 𝑣𝑛𝑣1 𝑣𝑗1 𝑣𝑗1 𝑣𝑛 onde a mesma é composta por duas partes separadas pelo símbolo Estas sequências serão a entrada do Problema da Maior Subsequência Comum considerando 𝑚 𝑉 𝑘 PASSO 2 Se existe retorne verdadeiro caso contrário retorne falso Note que os vértices contidos na maior subsequência comum são vértices que não possuem arestas entre si pois caso contrário eles não seriam comuns a todas as strings Desta forma estes vértices formam o maior conjunto independente do grafo Portanto os demais vértices formam a menor cobertura de vértices 𝐺 Dado a maior subsequência comum verifique para cada sequência que está associada a uma aresta se a mesma está na primeira parte da sequência ou 𝑣𝑖 𝑣𝑗 na segunda Se estiver na primeira parte adicione no conjunto Caso contrário 𝑣𝑖 𝐶 adicione no conjunto Ao final deste procedimento temos que contém uma 𝑣𝑗 𝐶 𝐶 cobertura de vértices g O passo 1 consiste em criar a sequência Cada sequência podem ser criado com passos ou seja com custo Como cada sequência está 2 𝑉 1 𝑂𝑉 associado a exatamente uma aresta temos um custo total de O passo 2 𝑂𝑉 𝐸 é simplesmente uma condicional que pode ser realizado em Portanto o custo 𝑂1 total é Portanto o procedimento de redução proposto é polinomial 𝑂𝑉 𝐸 h Como o Problema da Maior Subsequência Comum pertence a NP e um problema NPCompleto Problema da Cobertura de Vértices pode ser reduzido ao mesmo em tempo polinomial então o LCS também pertence a classe NPCompleto A implicação disto é que provavelmente exista uma dificuldade em encontrar uma abordagem eficiente em tempo computacional para o problema no caso geral Porém caso encontre um algoritmo polinomial que resolve o problema então todo problema da classe NPCompleto também possuirá um algoritmo polinomial mostrando que 𝑃 𝑁𝑃 Referências CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002 PAOLI A R Um estudo avançado do problema da Maior Subsequência Comum Trabalho de Conclusão de Curso Universidade Federal da Bahia 2016 PEVIANI C R T Algoritmos paralelos realísticos para a maior subsequência comum Dissertação de Mestrado Universidade Federal do Mato Grosso do Sul 2009 Atividade NPCompletude Longest Common Subsequence Problem a Uma sequência pode ser compreendida como o encadeamento ordenado de objetos naturais representados por símbolos comumente caracteres alfanuméricos Uma subsequência consiste em uma sequência contida em uma sequência maior e pode ser obtida extraindose zero ou mais caracteres da sequência original mantendo seu ordenamento Definese subsequência comum a duas ou mais sequências como uma sequência que é subsequência de todas as sequências PAOLI 2016 O problema da Maior Subsequência Comum LCS Longest Common Subsequence consiste em dado n2 sequências S1S2Sn determinar a maior subsequência de comum as n sequências Um instância do problema pode ser obtida considerando n3 S1ASTA S2PANPSPA e S3NAPPSAT A maior subsequência comum a estas três subsequências é ASA b O problema possui aplicações na área de biologia molecular onde é utilizado para comparação de sequências de DNA e no mapeamento de proteínas Também possui em ambientes que visam fazer correção ortográfica ou versionamento de arquivos PEVIANI 2009 c O problema possui solução polinomial quando n2 onde é possível aplicar a técnica de Programação Dinâmica Para caso n2 o problema pode ser resolvido por uma abordagem mas de tempo exponencial Considere k 1k2k n os tamanhos das n sequências Selecione a sequência Si de menor tamanho ou seja k ik j para todo j 1n Gere todas as 2 ki subsequências de Si Para toda subsequência de Si verifique se também é subsequência de S j para todo j 1n custo Oki Selecione a maior das subsequências comuns as n sequências Logo a complexidade desta abordagem é de O Este algoritmo pode ser eficiente se tivermos sempre a garantia que sempre existirá uma subsequência pequena No caso geral o algoritmo é pouco eficiente Abordagens heurísticas e metaheurísticas são utilizadas quando se deseja obter uma boa solução em tempo não proibitivo porém abrindo mão da garantia da otimalidade d Problema de decisão associado dado n2 sequências S1S2Sn e um inteiro m verifica se existe uma subsequência comum as n sequências de tamanho pelo menos m Precisamos provar que dado uma instância e uma possível solução do problema de decisão associado é possível construir um verificador em tempo polinomial Dado S1S2Sn m e uma possível solução S faça o seguinte procedimento PASSO 1 Verifique se S m PASSO 2 Para todo i1n verifique se S é uma subsequência de Si Percorra as sequência Si e S da esquerda para direita Verifique se o símbolo coincide com o símbolo observado na sequência S Caso afirmativo percorra um símbolo da sequência S Caso contrário continue com o mesmo símbolo Ao final de cada iteração percorra um símbolo de Si Se ao final das iterações S for percorrido completamente significa que S é subsequência de Si PASSO 3 Se S é subsequência de todo Si com i1n então S é uma subsequência comum as n sequências O procedimento acima é um procedimento verificador Os passos 1 e 3 podem ser realizado em tempo constante O1 Já o passo 2 tem um custo O onde pé o tamanho da maior sequência Desta forma o procedimento total tem custo Onp ² ou seja tem custo polinomial Portanto LCS NP e O problema selecionado foi o Problema da Cobertura de Vértices VCP Vertex Cover Problem Uma cobertura de vértices de um grafo não orientado GV E é um subconjunto V V tal que uv E então uV ou vV ou ambos Isto é cada vértice cobre suas arestas incidentes e uma cobertura de vértices para G é um conjunto de vértices que cobre todas as arestas em E O problema da cobertura de vértices visa determine o menor conjunto de vértices que é uma cobertura de vértices do grafo G CORMEN 2002 Problema da decisão associado Dado um grafo não orientado GV E e um inteiro t verifica se existe uma cobertura de vértices do grafo G de tamanho no máximo t f Abaixo é descrito o procedimento que mapeia uma entrada do Problema de Cobertura de Conjuntos em uma entrada do Problema da Maior Subsequência Comum Dado um grafo não orientado GV E e um inteiro k Queremos determinar se existe uma cobertura de vértices do grafo G de tamanho no máximo t Vamos considerar que G não possui vértices isolados Considere uma ordenação do conjunto de vértices Vv1v2vn PASSO 1 Para toda aresta viv j cria a sequência v1vi1vi1vnv1v j1v j1vn onde a mesma é composta por duas partes separadas pelo símbolo Estas sequências serão a entrada do Problema da Maior Subsequência Comum considerando mV k PASSO 2 Se existe retorne verdadeiro caso contrário retorne falso Note que os vértices contidos na maior subsequência comum são vértices que não possuem arestas entre si pois caso contrário eles não seriam comuns a todas as strings Desta forma estes vértices formam o maior conjunto independente do grafo G Portanto os demais vértices formam a menor cobertura de vértices Dado a maior subsequência comum verifique para cada sequência que está associada a uma aresta viv j se a mesma está na primeira parte da sequência ou na segunda Se estiver na primeira parte adicione vi no conjunto C Caso contrário adicione v j no conjunto C Ao final deste procedimento temos que C contém uma cobertura de vértices g O passo 1 consiste em criar a sequência Cada sequência podem ser criado com 2V 1 passos ou seja com custo O Como cada sequência está associado a exatamente uma aresta temos um custo total de O O passo 2 é simplesmente uma condicional que pode ser realizado em O1 Portanto o custo total é O Portanto o procedimento de redução proposto é polinomial h Como o Problema da Maior Subsequência Comum pertence a NP e um problema NPCompleto Problema da Cobertura de Vértices pode ser reduzido ao mesmo em tempo polinomial então o LCS também pertence a classe NPCompleto A implicação disto é que provavelmente exista uma dificuldade em encontrar uma abordagem eficiente em tempo computacional para o problema no caso geral Porém caso encontre um algoritmo polinomial que resolve o problema então todo problema da classe NPCompleto também possuirá um algoritmo polinomial mostrando que PNP Referências CORMEN T H et al Algoritmos teoria e prática Editora Campus v 2 p 296 2002 PAOLI A R Um estudo avançado do problema da Maior Subsequência Comum Trabalho de Conclusão de Curso Universidade Federal da Bahia 2016 PEVIANI C R T Algoritmos paralelos realísticos para a maior subsequência comum Dissertação de Mestrado Universidade Federal do Mato Grosso do Sul 2009