A arte de provar a complexidade de algoritmos

A teoria da complexidade, grosseiramente falando, preocupa-se em classificar os problemas computacionais de acordo com a sua dificuldade, assim, existem problemas resolvidos em tempo polinomial e aqueles resolvidos em tempo exponencial. Daí, temos as classes dos problemas P, NP, NP-completos, NP-difíceis e vários outros.

Provar que um problema é mais difícil que outro uma vez que não se encontrou um algoritmo que o resolve em tempo polinomial, consiste em transformar um problema que já se sabe da sua dificuldade para que ele seja resolvido pelo problema que se deseja provar a NP-completude ou NP-dificuldade.

O texto abaixo contém algumas dicas muito interessantes retiradas do livro The Algorithm Design Manual, tais dicas aconselham como proceder nestas demonstrações.

Provar que algoritmos são difíceis é uma habilidade. Mas uma vez que se pega o jeito, pode ser até simples de fazer reduções. De fato o pequeno segredo sujo sobre provas de NP-completude é que são elas são mais fáceis de criar do que de explicar, do mesmo jeito que algumas vezes é mais fácil reescrever um determinado código do que entender e modificá-lo.

Segue abaixo alguns conselhos para provar a dificuldade de um problema:

Faça o seu problema de origem ser o mais simples e restrito possível.

Nunca tente usar o problema geral do Caixeiro Viajante como o problema de origem. É melhor usar o problema do Circuito Hamiltoniano, ou melhor ainda, escolher Caminho Hamiltoniano ao invés de Circuito. O melhor de todos é usar o caminho hamiltoniano em um grafo planar direcionado onde cada vértice tem grau 3 (Isso sim é ser restrito 🙂 ). Todos esses problemas são igualmente difíceis e quanto mais restrito for o problema que se está reduzindo, menos trabalho a redução tem que fazer.

Faça o seu problema alvo o mais difícil possível.

Não esqueça de adicionar restrições ou liberdades extras afim de tornar seu problema mais geral. Um problema em grafo direcionado pode ser generalizado em um problema de grafo não direcionado, a partir daí pode ser mais fácil provar a complexidade. Uma vez que se tem uma prova da dificuldade do problema geral, você pode então voltar e tentar simplificar o problema alvo.

Selecione o problema de origem correto pela razão certa.

Selecionar o problema de origem certo faz uma grande diferença em quão difícil será provar que o problema é difícil. Embora, teoricamente, um problema particular é tão bom quanto qualquer outro, esta é a maneira mais fácil de dar errado. Algumas pessoas tentam provar que um problema é difícil procurando entre dezenas de opções qual é a mais ajustável, isso é coisa de amador, provavelmente não reconhecerão o que estão procurando quando ver.

O autor explica que utiliza apenas quatro candidatos a problema de origem. Ao limitar em quatro é possível conhecer muito mais cada um destes problemas. São eles:

  1. 3SAT: O velho confiável. Quando nenhum dos outros três abaixo são apropriados.
  2. Partição de Inteiros: Para problemas cuja dificuldade parece depender de números muito grandes.
  3. Cobertura de Vértices: Para problemas em grafo cuja dificuldade depende de seleção.
  4. Caminho Hamiltoniano: Para problemas em grafo cuja dificuldade depende de ordem.

Quando empacar, alterne entre procurar por um algoritmo ou uma redução.

As vezes a razão de você não provar a dificuldade de um problema é que existe um algoritmo eficiente que o resolve. Técnicas como programação dinâmica ou redução para problemas de grafos de tempo polinomial, tais como emparelhamento ou fluxo de rede, as vezes produzem algoritmos polinomiais surpreendentes. Se você não pode provar a dificuldade, provavelmente compensa mudar de opinião ocasionalmente.

Comentar

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s