Complexidade computacional: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
Linha 9:
 
===Instâncias de Problema===
Um [[problema computacional]] pode ser visto como uma coleção infinita de ''instâncias'' em conjunto com uma ''solução'' para cada instância. A sequência de entrada para um problema computacional é referido como uma instância do problema, e não deve ser confundido com o problema em si. Na teoria da complexidade computacional, um problema se refere à questão abstrata para ser resolvido. Em contraste, uma instância deste problema é uma expressão concreta, que pode servir como entrada para um problema de decisão. Por exemplo, considere o problema de teste de primalidade. A instância é um número (por exemplo, 10), o problema é determinar a primalidade de qualquer entrada, e a solução é "sim" se o número é primo e "não" se for o contrário (neste caso "não"). Alternativamente, a instância é uma entrada especial para o problema, e a solução é a saída correspondente à entrada.
 
Para realçar ainda mais a diferença entre um problema e uma instância, considere a seguinte instância da versão de decisão do [[problema do caixeiro viajante]]: Existe um percurso de, no máximo, 2000 km de comprimento passando por todas as 15 maiores cidades da Alemanha? A resposta a esta determinada instância do problema é de pouca utilidade para a resolução de outras instâncias do problema, como pedir uma ida e volta através de todos os lugares de Milão cujo comprimento total é no máximo 10 km. Por esta razão, a teoria da complexidade aborda problemas computacionais e não instâncias particulares do problema.