dam2

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sabendo que a linguagem CAIXEIRO_VIAJANTE(G), capaz de computar uma solução para o problema do caixeiro viajante sobre um grafo G, é NP-completa, um programador propôs o seguinte relaxamento:

Dado um grafo com V vértices, em vez de se calcular a solução ótima, que é obter o ciclo hamiltoniano cujo caminho é o de menor tamanho, uma solução muito boa seria utilizar N caixeiros e fazê-los resolver o problema para apenas V/N vértices do grafo original, assegurando-se de que não haja caixeiros compartilhando vértices.

Uma linguagem auxiliar útil a este relaxamento poderia ser do formato CAIXEIRO_PARCIAL(G, N). Neste sentido, o uso CAIXEIRO_PARCIAL(G, 7), por exemplo, retornaria um ciclo para um caixeiro viajante, que passa por apenas 1/7 dos vértices de G.

Dado tal cenário, considere as seguintes afirmações:

(I) A linguagem CAIXEIRO_PARCIAL(G, N) também é NP-completa.

(II) Para verificar se a linguagem CAIXEIRO_PARCIAL(G, N) é NP-completa, basta reduzi-la à linguagem CAIXEIRO_VIAJANTE(G).

(III) A linguagem CAIXEIRO_PARCIAL(G, N) é certamente NP.

(IV) Com a disponibilidade de processadores multicore e da programação multithread, pode ser que o relaxamento proposto seja computado em tempo polinomial, desde que se paralelize a computação dos N caixeiros.

Escolha a alternativa CORRETA:

1. Todas as afirmações são verdadeiras.
2. Apenas a afirmação III é verdadeira.
3. Apenas as afirmações I, II e III são verdadeiras.
4. Apenas as afirmações I e III são verdadeiras.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira