Livro Texto: ALGORITMOS - Teoria e Prática
Capítulo 34 - Problemas NP-completos
Redator: André Santanchè
 

Dê uma definição formal para o problema de encontrar o ciclo simples mais longo em um grafo não orientado {a}. Forneça um problema de decisão relacionado {b}. Forneça a linguagem correspondente ao problema de decisão {c}.

{a}

Ciclo simples: Dado um grafo G=(V,E) não orientado, um ciclo simples é uma lista ordenada de vértices (v1, v2, ..., vx) pertencentes a G, tal que x>=3 e existe um caminho simples <v1, ..., vx-1> além de uma aresta (vx-1, vx).

Ciclo simples mais longo: Considerando que o grafo G é ponderado, chamaremos de peso do ciclo simples w(c) a soma do peso de todas as arestas que pertencem ao ciclo c. Um problema de ciclo simples de maior peso em G, que chamamos LONG-CYCLE, consiste em encontrar um ciclo simples pertencente a G, cujo peso w(c) é o maior entre todos os valores de w(x), para qualquer ciclo simples x pertencente a G (se o grafo não for ponderado considera-se o mesmo raciocínio atribuindo-se o peso 1 a cada aresta).

{b}
Um problema de decisão CYCLE relacionado com LONG-CYCLE é tal que, para uma instância do problema de decisão (G, k):

• CYCLE(G, k) = 1 (sim) se para o ciclo simples mais longo c pertencente a G, w(c) >= k.
• CYCLE(G, k) = 0 (não) em caso contrário.

{c}

O algoritmo de programação dinâmica para o problema da mochila 0-1 que é apresentado no Exercício 16.2-2 é um algoritmo de tempo polinomial? Explique sua resposta. 

Não, pois para uma entrada de magnitude O(n.lg W) o tempo de execução do algoritmo é O(n.W). Isto caracteriza uma relação exponencial entre o tamanho da entrada e o tempo de execução.

A magnitude da entrada é calculada sabendo-se que n é o número de itens e W é o peso máximo que algum item pode ter. Codificando em binário um valor numérico que pode variar de 0 até W, ele ocupará no máximo teto(lg W) bits, deste modo o tamanho da entrada será O(n.lg W).

Mostre que um algoritmo que efetua no máximo um número constante de chamadas a sub-rotinas de tempo polinomial é executado em tempo polinomial, mas que um número polinomial de chamadas a sub-rotinas de tempo polinomial pode resultar em um algoritmo de tempo exponencial.

Quando um algoritmo executa um número constante K de chamadas a uma sub-rotina, que executa em tempo polinomial de acordo com o tamanho de uma entrada fixa, o tempo de execução resultante do algoritmo será de ordem K vezes o tempo de execução da sub-rotina, o que resultará em um tempo polinomial (por ser K uma constante ela não interfere na ordem de crescimento quando multiplicada pelo polinômio).

Quando um algoritmo executa um número polinomial de chamadas a uma sub-rotina e o tamanho da entrada que o algoritmo repassa para a sub-rotina cresce exponencialmente, o tempo total de execução do algoritmo pode se tornar exponencial. Abaixo um exemplo de algoritmo:

SUPERCONCATENA
    a <- "xx"
    for i <- 1 to n do
        a <- CONCATENA(a, a)

Note que o algoritmo SUPERCONCATENA executa n vezes a sub-rotina CONCATENA, cujo tempo de execução é O(m), sendo m a soma dos comprimentos das cadeias de entrada. Como o tamanho da cadeia armazenada na variável a dobra a cada chamada de CONCATENA, quando o valor da variável i for igual a n, o tamanho da entrada será 2^n, caracterizando um tempo exponencial de execução.

Se por outro lado utilizarmos este mesmo algoritmo com um número constante K no lugar de n, o tamanho da entrada na última chamada de CONCATENA será 2^K. Como K é uma constante, 2^K também é uma constante, não caracterizando um algoritmo de tempo exponencial.