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

["Lucas Prado Melo" <lucaspm@xxxxxxxxxxx>]

Não achei pedante, achei as informações muito legais!
Você sabe se existe alguma lista parecida com esta da obm mas para
discussões de computação?

abraços

On Dec 24, 2007 12:47 AM, Maurício Collares <mauricioc@xxxxxxxxx> wrote:
>
> 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
> =========================================================================
>

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