|
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.
|
