[SPAM] [obm-l] Res: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Demonstrações

[Rodrigo Cientista <rodrigocientista@xxxxxxxxxxxx>]

SPAM: -------------------- Start SpamAssassin results ----------------------
SPAM: This mail is probably spam.  The original message has been altered
SPAM: so you can recognise or block similar unwanted mail in future.
SPAM: See http://spamassassin.org/tag/ for more details.
SPAM: 
SPAM: Content analysis details:   (6.40 hits, 5 required)
SPAM: X_MAILING_LIST     (-0.3 points) Found a X-Mailing-List header
SPAM: SPAM_PHRASE_00_01  (0.8 points)  BODY: Spam phrases score is 00 to 01 (low)
SPAM:                    [score: 0]
SPAM: QUOTED_EMAIL_TEXT  (-0.8 points) BODY: Contains what looks like a quoted email text
SPAM: SUPERLONG_LINE     (0.0 points)  BODY: Contains a line >=199 characters long
SPAM: FORGED_YAHOO_RCVD  (1.4 points)  'From' yahoo.com does not match 'Received' headers
SPAM: RCVD_IN_ORBS       (2.2 points)  RBL: Received via a relay in orbs.dorkslayers.com
SPAM:                    [RBL check: found 158.38.190.206.orbs.dorkslayers.com., type: 68.178.232.99]
SPAM: RCVD_IN_OSIRUSOFT_COM (0.4 points)  RBL: Received via a relay in relays.osirusoft.com
SPAM:                    [RBL check: found 158.38.190.206.relays.osirusoft.com.]
SPAM: X_OSIRU_OPEN_RELAY (2.7 points)  RBL: DNSBL: sender is Confirmed Open Relay
SPAM: 
SPAM: -------------------- End of SpamAssassin results ---------------------

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 <sms.sergio@xxxxxxxxx>
Para: obm-l@xxxxxxxxxxxxxx
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: <rodrigocientista@xxxxxxxxxxxx>
To: <obm-l@xxxxxxxxxxxxxx>
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: <arcguede@xxxxxxxxx>
> To: <obm-l@xxxxxxxxxxxxxx>
> 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.
> >
> > rodrigocientista@xxxxxxxxxxxx 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"
> >> <sms.sergio@xxxxxxxxx>
> >> To: "Lista OBM" <obm-l@xxxxxxxxxxxxxx>
> >> 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
=========================================================================