Questão 67240

Um professor de Algoritmos e Estruturas de Dados está lecionando sobre a classe de problemas NP (Nondeterministic Polynomial time) e o conceito de NP-Completude. Ele quer que seus alunos de graduação, futuros professores, tenham uma compreensão intuitiva, ainda que simplificada, de um dos problemas mais profundos da ciência da computação: a questão P vs. NP. Para isso, ele evita uma abordagem puramente matemática e foca em exemplos. Ele apresenta um trecho adaptado de 'Grokking Algorithms' de Aditya Bhargava: "Problemas na classe P são aqueles que podemos resolver rapidamente (em tempo polinomial). Problemas na classe NP são aqueles cujas soluções, uma vez encontradas, podemos verificar rapidamente se estão corretas. Todo problema P também é NP. A grande questão é se P = NP. Ou seja, se um problema cuja solução pode ser verificada rapidamente também pode ser resolvido rapidamente. Os problemas NP-Completos são os 'mais difíceis' da classe NP. Se alguém encontrar uma solução rápida para *qualquer* problema NP-Completo, essa solução poderia ser adaptada para resolver rapidamente *todos* os problemas NP." Ele então apresenta dois problemas clássicos aos alunos:

Problema 1 (Ordenação): Dada uma lista de $n$ números, ordená-la em ordem crescente. Problema 2 (Caixeiro Viajante): Dadas $n$ cidades e as distâncias entre elas, encontrar o menor caminho possível que visite cada cidade exatamente uma vez e retorne à origem.

A tarefa dos alunos é classificar os problemas e analisar a natureza de suas soluções.

I. O Problema 1 (Ordenação) está na classe P, pois existem algoritmos eficientes, como o Merge Sort, que o resolvem em tempo $O(n \log n)$, que é tempo polinomial. A verificação da solução (checar se a lista está ordenada) também é rápida, $O(n)$.

II. O Problema 2 (Caixeiro Viajante) é um exemplo clássico de um problema NP-Completo. Não se conhece nenhum algoritmo eficiente (polinomial) para encontrar a solução ótima para todas as instâncias. No entanto, se alguém lhe apresentar um caminho (uma solução), você pode verificar rapidamente (em tempo polinomial) se ele é válido e qual o seu custo total.

III. A diferença fundamental entre os dois, do ponto de vista prático e pedagógico, é que para o Problema 1, podemos ensinar um algoritmo que garante encontrar a solução ótima de forma eficiente. Para o Problema 2, para instâncias grandes, ensinamos os alunos a usar 'heurísticas' ou 'algoritmos de aproximação', que encontram soluções 'boas o suficiente', mas não necessariamente as ótimas, pois encontrar a ótima é computacionalmente intratável.

É correto o que se afirma em: