21/06/2017 21:38, postada por Vinícius Paes de Camargo

NP-Completo

NP-Completo

Em teoria da complexidade computacional, estuda-se a classificação de problemas computacionais conforme sua dificuldade inerente, ou seja, a quantidade de recursos (tempo, espaço, entre outros) necessários para se resolver o problema usando o melhor algoritmo possível (mesmo que este seja desconhecido).

Existem diversos tipos de problemas e classes de complexidade. Neste texto consideraremos apenas problemas de decisão, ou seja, problemas que admitem apenas respostas sim ou não para suas instâncias. Por exemplo, o problema de determinar se um número x é composto (quando tem mais de dois divisores naturais distintos), para a instância 6 a resposta é sim, para a instância 13 a resposta é não. Destacaremos uma classe usada para distinguir problemas computacionalmente tratáveis dos intratáveis em termos de tempo de processamento.

Informalmente, um problema tratável é um problema que pode ser resolvido por meio de um algoritmo que devolve a solução em tempo razoável. Já um problema intratável, embora possa existir um algoritmo que o resolva, o tempo necessário para resolvê-lo inviabiliza seu uso. Em termos teóricos, definimos a complexidade de um algoritmo em função do tamanho da entrada do problema. Assim, se o tempo  consumido pelo algoritmo em função do tamanho da entrada for limitado por uma função polinomial (ou seja, ter uma entrada que seja no máximo de tamanho nk, para k constante), dizemos que o problema é tratável e pertence à classe P (Deterministic Polynomial Time).

Ocorre que, algumas vezes, podemos não conhecer um algoritmo que resolva um problema em tempo polinomial, mas saberíamos verificar em tempo polinomial se um determinado conjunto de dados (chamado certificado) seria a solução para uma instância do problema.  Problemas que podem ser verificados em tempo polinomial pertencem à classe NP (do acrônimo em inglês Nondeterministic Polynomial Time).

Todos os problemas na classe P podem ser verificados em tempo polinomial e, portanto, estão contidos na classe NP. No entanto, não se sabe se NP é um conjunto próprio   (P = NP?). Em outras palavras, será que verificar a solução para um problema é tão complexo quanto resolvê-lo? Este é o problema mais importante da área de Computação em aberto.

Para aprofundar o entendimento e organizar a discussão sobre o assunto, introduziremos a principal classe usada na classificação de problemas tratáveis e intratáveis, a classe NP-Completo, definida como sendo o conjunto de todos os problemas de decisão cujas soluções podem ser verificadas em tempo polinomial usando uma máquina de Turing determinística, além de serem tão difíceis quanto quaisquer outros problemas presentes no conjunto NP (i. e. todos os problemas pertencentes a NP são redutíveis em tempo polinomial a qualquer problema na classe NP-Completo). Sendo uma redução em tempo polinomial de um problema A para um problema B um algoritmo que transforma em tempo polinomial uma instância de entrada x do problema A em uma instância de entrada y do problema B, tal que x é uma instância que produz resposta sim para A se e somente se y é uma instância que produz resposta sim para B. Deste modo, podemos resolver o problema A por meio desta transformação e devolução do resultado do algoritmo que resolve B.

Existe a imensa vontade e esforço para que prove-se que um problema NP-Completo pode ser resolvido em tempo polinomial por máquina determinística, já que isso levaria todos os demais problemas em NP a serem resolvidos em tempo polinomial, economizando muito processamento para algoritmos computacionalmente complexos e quebrando inclusive uma parte da criptografia hoje existente.

Abaixo seguem alguns exemplos de problemas NP-Completo:

Satisfatibilidade

O primeiro problema encontrado na classe do NP-Completo é o problema da Satisfatibilidade. Ele caracteriza-se por dada uma proposição booleana com n variáveis, verificar se há alguma atribuição de valores verdade (V ou F) para as variáveis tal que a proposição seja verdadeira. Sua caracterização como NP-Completo se dá pois para que se descubra se ele pode retornar verdadeiro tem a necessidade de montar sua tabela verdade, e para a montagem da tabela verdade são necessárias 2n linhas, assim se alguma das linhas resultar em verdadeiro, o problema é satisfatível. Por exemplo uma instância de 20 variáveis, seriam geradas 220linhas, que culminariam em 1.048.576 (1 milhão de linhas).

Soma dos subconjuntos

Seja um conjunto C de números e um K inteiro, há um subconjunto D contido em C tal que a soma seja igual a K? A partir desta formulação conclui-se que um problema relativamente simples exige demasiadas comparações, pois, supondo que temos apenas um elemento no conjunto, pode-se formar dois subconjuntos, isto é, ele e o conjunto vazio. Se adicionarmos mais um elemento neste conjunto, temos a possibilidade de formar um subconjunto com cada um dos subconjuntos já feitos com o novo elemento. Temos então 22 subconjuntos a partir de um conjunto de dois elementos. Seguindo essa lógica, um conjunto de n elementos gera 222...2 subconjuntos, com n números 2, isto é, 2n subconjuntos. Pode parecer fácil, mas com 20 elementos (n = 20), e um K qualquer, já são formados 220 subconjuntos, isto é, mais de 1 milhão de combinações.

Caixeiro Viajante

O problema do caixeiro viajante é de maneira simples: dado um número n de cidades, o caixeiro tem que sair de uma cidade e voltar para a mesma passando por todas as outras cidades percorrendo a menor distância possível, sabendo que tem se deslocar de uma cidade para qualquer outra. É fácil descobrir a quantidade de possíveis combinações que se pode obter desse problema, pois, visto que a cidade em que ele se encontra não conta, tem-se n-1 cidades para se deslocar, depois n-2, e assim por diante, até que sobre apenas uma cidade para se visitar antes de retornar para a cidade inicial. A quantidade de combinações possíveis é dada pela expressão fatorial: (n-1)!. O problema de decisão consiste em saber se é possível percorrer todas as cidades com custo menor ou igual a um valor k.

Feito isso, é necessário somar as distâncias percorridas entre as cidades em cada uma destas possíveis rotas e descobrir se alguma delas possui custo menor ou igual a k. Parece fácil, porém o fatorial cresce incrivelmente rápido, visto que n = 20 nos dá 61017ou seja 620.000.000.000.000.000 (620 quadrilhões combinações).

Você pode encontrar esses e outros problemas NP-Completos em http://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html.

Caso você consiga resolver um destes problemas em tempo polinomial, comunique as autoridades, pois você provou que P = NP e conseguirá 1 milhão de dólares do CLAY, já que resolveu um dos “Problemas do Milênio”. Se tiver interesse em conhecer os outros Problemas do Milênio, acesse o link: http://www.claymath.org/millennium-problems