|
Oi pessoal
Queria perguntar ao Nicolau ou a quem conseguir me
resolver essa pergunta:
Se um algoritmo pode construir uma sequência
randômica, uma sequência qualquer desse tipo com um número finito n de
termos poderia então ser descrita por uma infinidade de algoritmos
diferentes, e esses algoritmos podem ser todos construidos a partir de um
algoritmo.(todos os algoritmos iriam variar de problema para problema). Ou
seja uma sequência pode ser construida por infinitos algoritmos diferentes, mas
todos esses algoritmos podem ser construidos a partir de um mesmo
algoritmo.
A problema é o seguinte: Dada uma sequência
qualquer, qual é o algoritmo que gera todos os outros?
A minha dúvida é que pelo o que posso ver esse
problema é um problema do tipo NP (polinominal não-determinístico), ou seja a
sua resposta existe mas é impossível de ser dada na prática.
O meu raciocínio para chegar a essa conclusão foi o
seguinte:
Primeiro é preciso provar que o problema tem
solução:
Sendo a sequência A=a,b,c,d,e,f,g,...,n (em que a é
o 1º termo, b é o 2º, até n que é o n-ésimo termo).
Sendo B o conjunto de algoritmos que geram
sequências em que quando o primeiro termo é a, o segundo é b e sendo C o
conjunto dos algoritmos para os quais se o 1º termo é b, o 2º é C.
O algoritmo que descreve a sequência A então
pertence à B intersecção com C. B e C possuem infinitos elementos.
Como a,b,c são 3 números aleatórios, B intersecção com C é aleatório. A
intersecção aleatória de 2 conjuntos infinitos é um conjunto infinito.
Expandindo esse raciocínio, existem infinitos algoritmos que perfazem A. Logo
existem infinitas alternativas a serem analisadas, ou seja o problema é do tipo
NP.
Esse pensamento esta certo?
Já vou agradecendo
André T.
|