MO417- QUESTÃO PARA A PROVA ORAL

Número: 2013-102

Enunciado: Qual das seguintes alternativas não representa um problema NP-Difícil?

1. Encontrar um caminho de comprimento máximo num grafo orientado
2. Encontrar um ciclo Hamiltoniano num grafo com n vértices e n arestas
3. O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos
4. A versão de SAT que também usa a operação XOR (onde X1 XOR X2 retorna 1 se e somente se X1 e X2 forem diferentes)
5. NDA

Ideia original de: Sheila Katherine Venero Ferro