Re: [obm-l] Algoritmo de Shor

[Chicao Valadares <chicaovaladares@xxxxxxxxxxxx>]

Só alguns esclarecimentos:

-A afirmaçao no qual um computador quantico fará em
"poucos segundos" o que um supercomputador levaria
milhoes de anos para fazer é verdadeira apenas para
problemas modelados via algoritmos POLINOMIAIS
nao-deterministicos(NP,Co-Np...) no qual não se
conhece algoritmo polinomial deterministico eficiente
para resolver, mas se conhece apenas o exponencial
deterministico que é muito custoso e as vezes o
polinomial probabilistico deterministico, que possui
um custo aceitavel.
-A contribuiçao do computador quantico para os
algoritmos seria justamente a IMPLEMENTAÇAO REAL do
não determinismo, algo impossivel com os modelos
atuais.Observe que PRIMOS, pertence a NP(na verdade
pertence a P contido em NP via AKS, mas nao vem ao
caso) e com o advento do computador quantico seria
possivel a implementaçao real do ALGORITMO EM NP para
PRIMOS.Entao o computador quantico resolveria PRIMOS
em tempo polinomial.
-Isto nao quer dizer que existam problemas dificeis
ate para computadores quanticos um exemplo seriam
algoritmos da classe NEXP(algoritmos nao
deterministicos de tempo exponenciais) que nao se sabe
se sao iguais a EXP(algoritmos deterministicos de
tempo exponenciais) e em caso afirmativo,existem
trabalhos indicando que implicaria tambem em P=NP.

É isso :)

--- Paulo Santa Rita <p_ssr@hotmail.com> escreveu: >
Ola Pessoal,
> 
> Numa mensagem anterior eu citei a COMPUTACAO
> QUANTICA como uma das possiveis 
> aplicacoes
> da Mecanica Quantica. A palavra "possivel" talvez
> seja muito modesta, pois 
> os resultados ja
> existentes nao obstante nao a colocarem como um
> campo de pesquisa ja 
> consolidado, sem duvida
> retiram-na do campo das meras especulacoes ...
> 
> UMA das possibilidades e a COMPUTACAO PARALELA,
> presente no ALGORITMO DE 
> SHOR. Quem deu inicio a tudo isso foi o Shor, hoje
> professor do MIT. O seu 
> famoso e bastante conhecido e discutido e a
> Matematica envolvida nele e 
> realmente elementar. Para ver isso,  entre em :
> 
> http://www-math.mit.edu/~shor
> CLIQUE EM : papers
> A SEGUIR CLIQUE EM : quantum computing
> E FINALMENTE CLIQUE EM : polynomial-time algorithms
> for prime factorization 
> ....
> 
> Um Computador Quantico fara em poucos minutos o que
> um Computador Classico ( 
> exemplo :
> um supercomputador atual ) contemporaneo gastaria
> dezenas de bilhoes de anos 
> pra fazer. Por
> outro lado, como nos estamos na Pre-historia da
> Computacao Quantica, o 
> numero de fatos
> relevantes e ideias importantes a serem descobertos
> e, muito provavelmente, 
> bem mais rico que
> num campo classito da Teoria da Computacao.
> 
> Um Abraco a Todos
> Paulo Santa Rita
> 4,1509,230604
> 
>
_________________________________________________________________
> MSN Messenger: converse com os seus amigos online.  
> http://messenger.msn.com.br
> 
>
=========================================================================
> Instruções para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
=========================================================================
>  

=====
"O Binômio de Newton é tão belo como a Vênus de Milo.
O que há é pouca gente para dar por isso... "
Fernando Pessoa - Poesias de Alvaro Campos

_________________________________________________________________
As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) 
são
para uso restrito, sendo seu sigilo protegido por lei. Caso não seja
destinatário, saiba que leitura, divulgação ou cópia são proibidas. 
Favor
apagar as informações e notificar o remetente. O uso impróprio será 
tratado
conforme as normas da empresa e a legislação em vigor. Agradecemos sua
colaboração.


The information mentioned in this message and in the archives attached 
are
of restricted use, and its privacy is protected by law. If you are not 
the
addressee, be aware that reading, disclosure or copy are forbidden. 
Please
delete this information and notify the sender. Inappropriate use will 
be
tracted according to company's rules and valid laws. Thank you for your
cooperation.

______________________________________________________________________

Yahoo! Mail - agora com 100MB de espaço, anti-spam e antivírus grátis!
http://br.info.mail.yahoo.com/
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================