|
No meu ponto de vista, existem infinitos algoritmos
para fazer alguma coisa. Até para não fazer nada.
Por exemplo, um algoritmo para calcular a+b.
Pode-se fazer da maneira tradicional, ou então pode-se fazer um loop percorrendo
os números, subtraindo b e verificando se é igual a 'a'.
Ou então pode-se somar 6 a 'a' somar 'b' ao
resultado e depois subtrair '6'.
Agora, em vez de fazer as operação acima com 6,
faça com todas os outros naturais. Como são constantes, haverá infinitos
algoritmos que fazem a soma.
Enfim, o meu raciocínio é por aí. Esse é mais um
motivo que as classes P e NP, por exemplo, são conjuntos de problemas e não
de algoritmos. Estudar algoritmos pode ser muito mais complicado.
Formalmente, em teoria da computação, podemos
definir um problema de decisão como uma linguagem. Um problema de decisão é um
cuja resposta é sim ou não. Uma linguagem pode ser considerada como um conjuntos
de seqüências de caracteres de um alfabeto. Podemos sempre escrever uma
instância de um problema como uma string em um alfabeto. Assim o problema
pode ser visto como um mapeamento de tais seqüências em {0,1}. A linguagem
associada ao problema contém todas as seqüências (e somente elas) que são
mapeadas em 1.
Assim todo problema de decisão fica reduzido ao
problema: Essa seqüência pertence a essa linguagem?
Isso facilita bastante a teoria.
Problemas de otimização podem ser reduzidos a
problemas de decisão utilizando busca binária com perguntas do tipo: O melhor
valor é melhor que k?
Maiores informações podem ser encontradas no texto
de Cook sobre o problema "P=NP?" no site www.claymath.org/prizeproblems
Uma outra observação é que nem todo problema
pertence necessariamente a NP. Pode ser que vc não consiga um algoritmo
polinomial em uma máquina não-determinística para ele.
Eu não entendi a conclusão: "Logo existem infinitas
alternativas a serem analisadas, ou seja o problema é do tipo NP."
Poderia tb me explicar o que é "intersecção
aleatória"?
Até mais
Vinicius
|