she

MO417- QUESTÃO PARA A PROVA ORAL

Número:  

Enunciado: Qual das seguintes alternativas não representa um problema NP-Completo?

a) Encontrar o caminho mais longo entre dois vértices de um grafo orientado
b) Encontrar um ciclo Hamiltoniano num grafo com |V| vértices e |V| arestas
c) O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos 
d)Um circuito no problema SAT que também use portas XOR (retorna 1 se X1 e X2 forem diferentes)
e) NDA

 Ideia original de: Sheila Katherine Venero Ferro