Acredito que o que o albert quer dizer é o seguinte: o problema do milênio 
relacionado aos problemas NP é demonstrar que um problema NP pode ser expresso 
em termos de um problema P (mas não necessariamente dar um exemplo disso).

Imagine uma empresa de entregas que deseja minimizar seus custos de frete, 
devendo-se para tal determinar qual a menor rota entre um município brasileiro 
e outro, passando por todos, nos seguinte termos:

Tempo para ir do município A ao B: x horas
Tempo para ir do município A ao C: y horas
Tempo para ir do município A ao D: z horas
.
.
.
Tempo para ir do município Y ao Z: n horas

supondo 27 municípios que permitam um caminho entre cada um deles, isto é, cada 
um se combina com todos os demais, todos formam duplas com todos, pra efeitos 
de simplificação.

neste sentido, todas rotas possíveis são em número = 27!

claramente a cada incremento de um município teremos um incremento muito maior 
de rotas a serem examinadas por um programa computacional qualquer, sendo este 
um problema com tempo de processamento não polinomial (NP)

agora imagine um problema em que pede-se pra calcular o tempo médio de cada 
rota que parte de A e termina em A, tal que cada rota seguinte seja escolhida 
dentre as com menor tempo, passando por todos os municípios pelo menos uma vez. 
Se formos aumentando o número de municípios o tempo de processamento crescrerá 
aritmeticamente. Este é um problema com tempo de processamento polinomial (P).

existe alguma forma de contruir-se uma máquina capaz de resolver problemas 
não-polinomiais como esses em tempos polinomiais? 

o problema do milênio pede que se demonstre apenas a possibilidade, não que se 
dê um exemplo concreto, acho q era isso que o albert estava querendo dizer com 
"demonstração de demonstração", o que em última análise poderia ser melhor 
expresso como "demonstração de possibilidade"


----- Mensagem original ----
De: Sérgio Martins da Silva <[EMAIL PROTECTED]>
Para: obm-l@mat.puc-rio.br
Enviadas: Domingo, 23 de Dezembro de 2007 18:21:50
Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Demonstrações

Caros Rodrigo e arcguede,

Poderiam me esclarecer o que demonstração de uma demonstração tem a ver com
problemas NP? Qual bibliografia recomendam sobre isso?

Abraços,

Sérgio

----- Original Message ----- 
From: <[EMAIL PROTECTED]>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, December 18, 2007 12:46 AM
Subject: [obm-l] Re: [obm-l] Re: [obm-l] Demonstrações


> Acredito que o problema NP seja provar que existe ou não uma forma
> matemática, objetiva, de transformar problemas NP (com tempo de
> processamento não polinomial) em problemas P (tempo de processamento
> polinomial). Correto?
>
> qual seria a remissão a que você se referiu?
>
> ----- Original Message ----- 
> From: <[EMAIL PROTECTED]>
> To: <obm-l@mat.puc-rio.br>
> Sent: Monday, December 17, 2007 2:16 AM
> Subject: Re: [obm-l] Re: [obm-l] Demonstrações
>
>
> > Acho que isso nos remete ao "terceiro problema do milênio" -  o problema
> > NP.
> >
> > [EMAIL PROTECTED] escreveu:
> >> Acredito que uma "demonstração de demonstração" seria algo como
> >> "chover no molhado". Uma demonstração está correta se, em última
> >> instância, está de acordo com os axiomas mais básicos da matéria.
> >> Então, uma demonstração de demontração recorreria, também em última
> >> análise, exatamente aos mesmos axiomas, sendo assim redundante.
> >>
> >> Se você fala inglês, aqui está um fórum onde há diversos debates
> >> interessantes sobre esses assuntos, além de resolução técnica de
> >> questões de matemática, física química, engenharia em geral, etc...
> >>
> >> http://www.physicsforums.com/
> >>
> >> abraços
> >>
> >> ----- Original Message ----- From: "Sérgio Martins da Silva"
> >> <[EMAIL PROTECTED]>
> >> To: "Lista OBM" <obm-l@mat.puc-rio.br>
> >> Sent: Sunday, December 16, 2007 10:56 PM
> >> Subject: [obm-l] Demonstrações
> >>
> >>
> >>> Doutores,
> >>>
> >>> Penso que a palavra mais comum nesta lista e, quiçá, da matemática é
> >>> "demonstração". Por isto, gostaria de saber como se demonstra que uma
> >>> demonstração está correta. E mais, que é completa. Quais são os
> >>> requisitos,
> >>> condições, etc ?
> >>>
> >>> Abraços,
> >>>
> >>> Sérgio
> >>>
> >>>
=========================================================================
> >>>
> >>> Instruções para entrar na lista, sair da lista e usar a lista em
> >>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> >>>
=========================================================================
> >>
> >>
> >>
=========================================================================
> >> Instruções para entrar na lista, sair da lista e usar a lista em
> >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> >>
=========================================================================
> >>
> >
> >
=========================================================================
> > Instruções para entrar na lista, sair da lista e usar a lista em
> > http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> >
=========================================================================
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================


      Abra sua conta no Yahoo! Mail, o único sem limite de espaço para 
armazenamento!
http://br.mail.yahoo.com/

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================

Responder a