Quais problemas que costumam ser exponenciais?

Passo 1

O enunciado pede para identificar problemas cujos algoritmos mais conhecidos exigem tempo de execução que cresce exponencialmente com o tamanho da entrada. O conteúdo aqui é complexidade de algoritmos, em particular casos em que surgem funções de tempo como 2^n ou n!.

Passo 2

Complexidade exponencial aparece sempre que precisamos enumerar todas as combinações ou permutações de um conjunto de tamanho n. Nesses casos o número de candidatos cresce como 2^n (todas as subsequências) ou como n! (todas as permutações).
Uma grande família de problemas de enumeração de subconjuntos inclui: subset sum (soma de subconjuntos), PARTITION (particionamento em dois subconjuntos de mesma soma), KNAPSACK (mochila) e até variações de corte mínimo. Esses algoritmos de força bruta costumam testar cada uma das 2^n opções.

Passo 3

Outra classe é a de permutações ou atribuições, como TSP (caixeiro viajante) que testa todas as n! rotas possíveis, e problemas de satisfatibilidade booleana (SAT/3-SAT) que verificam todas as 2^n atribuições de variáveis.
Nos grafos, muitos problemas NP-completos também são exponenciais: HAMILTONIAN PATH/CYCLE (caminho/ciclo hamiltoniano), CLIQUE (maior subgrafo completo), VERTEX COVER, GRAF COLOURING (coloração de vértices), STEINER TREE e várias versões de escalonamento de tarefas.

Passo 4

Em resumo, sempre que um problema é NP-completo e não se conhece algoritmo polinomial, a solução exata via força bruta tende a ser exponencial, explorando todas as configurações possíveis.

Resposta

Problemas que costumam ser exponenciais incluem aqueles que exigem enumeração de 2^n combinações (Subset Sum, PARTITION, KNAPSACK), de n! permutações (TSP), de 2^n atribuições booleanas (SAT/3-SAT) e muitos problemas NP-completos de grafos como HAMILTONIAN PATH/CYCLE, CLIQUE, VERTEX COVER, GRAPH COLOURING e STEINER TREE.

Exercícios relacionados