Questão para a Prova Oral 176

Semana: 09/06/2003 a 13/06/2003

Assunto: Fluxo máximo (Parte 2) e NP completude (Parte 1)

Enunciado
Qual dos seguintes problemas NÃO é um problema NP completo:

A) Determinar se uma fórmula 3-CNF é capaz de satisfação ou não.
B) Encontrar caminhos mais curtos a partir de uma única origem em um grafo orientado.
C) Encontrar o caminho simples mais longo entre dois vértices em um grafo orientado.
D) Determinar se um grafo orientado tem um ciclo hamiltoniano ou não.
E) N.D.A.

Marcelo Fantinato
RA: 000472