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
ou
.
Passo 2
Complexidade exponencial aparece sempre que precisamos enumerar todas as combinações ou permutações de um conjunto de tamanho
. Nesses casos o número de candidatos cresce como
(todas as subsequências) ou como
(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 opçõ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
Passo 3
Outra classe é a de permutações ou atribuições, como TSP (caixeiro viajante) que testa todas as
rotas possíveis, e problemas de satisfatibilidade booleana (SAT/3-SAT) que verificam todas as
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.
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
combinações (Subset Sum, PARTITION, KNAPSACK), de
permutações (TSP), de
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.