[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Res: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Demonstrações
- To: obm-l@xxxxxxxxxxxxxx
- Subject: Re: [obm-l] Res: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Demonstrações
- From: "Maurício Collares" <mauricioc@xxxxxxxxx>
- Date: Sun, 23 Dec 2007 23:47:55 -0300
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; bh=yqUQ5PQw5prhyO9cSAzh93kQW8EGrtyDYOvayMocLEc=; b=IKMhb9DdukZBE8a4Suj+y1SIqztsaL0DzNb/vs+lRuEAKsn/l6WEOmXunQ1KOkI1C0YeW+6KfMLYao01mmkinkn/0lhDvNoybVeuob4ObU+bk6VDycgcFzGzI6F5U1V72M8FdGu9KminoymusCHgMrh/94YuCDfZ/xyU6W/ByVo=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=IqhNWZXTOEx2sdIcZlWI4QxIiI8N7HOpcUu1l/O6Bj21/DKqBbTIQO39aAtXewcaJKTSG3m7dh7vPpqzpJMbKvjaAVWvu65KHwi+hBp0SNIzLOaURzVOKk1KcE5hzE0b7rWmDhM9fqaDN+aAHxCjtWXCrjRdTr58q2G5uKrMZ0M=
- In-reply-to: <680082.12206.qm@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
- References: <680082.12206.qm@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Reply-to: obm-l@xxxxxxxxxxxxxx
- Sender: owner-obm-l@xxxxxxxxxxxxxx
On Dec 23, 2007 11:04 PM, Rodrigo Cientista
<rodrigocientista@xxxxxxxxxxxx> wrote:
> 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)
Só uma observação pedante: NP não significa não-polinomial. NP é a
classe de todos os problemas que podem ser resolvidos em tempo
polinomial numa máquina de Turing não-determinística. Uma formulação
alternativa é a seguinte: um problema está na classe de complexidade
NP se, dada uma possível resposta, uma máquina de Turing
determinística consegue *verificar* a veracidade da mesma em tempo
polinomial. Em particular, a classe de complexidade NP contém a classe
de complexidade P, que é a classe dos problemas que podem ser
resolvidos em tempo polinomial por uma máquina de Turing
determinística.
Existe também a classe dos problemas NP-difíceis, que pode ser
descrita assim: Se um computador pudesse resolver um problema
NP-difícil (basta saber resolver um tipo de problema), ele poderia
resolver qualquer problema da classe NP em tempo polinomial. Além
disso, a classe NP-completo é a interseção da classe NP com a classe
NP-difícil.
Quanto a pergunta original, não consegui entender a relação da classe
de complexidade NP com a dúvida do Sérgio (se alguém pudesse me mandar
alguma referência sobre isso, ficaria agradecido), mas existem coisas
interessantes quanto a verificação computadorizada de provas de
teoremas; o programa mais famoso para fazer isso é o Coq. Além disso,
existe um site bastante interessante chamado Metamath
(<http://us.metamath.org>) com um monte de proposições matemáticas
escritas de um modo bastante cru, propício para verificação
automática. Dá pra perder horas clicando nas várias proposições até
chegar aos axiomas ZFC.
--
Abraços,
Maurício
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================