[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



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
=========================================================================