Acessar o Zé Moleza
ou
O que você está pesquisando?
Classe de Problemas – Problema P versus NP
3079 visualizações
3598 palavras
Adicionar aos favoritos
Loading...- | |
Classe de Problemas - Problema P versus NP
Introdução
A questão de decidibilidade de soluções para uma determinada função, é uma questão tratada por uma parte especial da Teoria da Computação, chamada de Teoria da Computabilidade , que faz referência ao tratamento das classes de problemas P, NP e NP Completo.
A teoria da computabilidade no fundo diferencia os problemas decidíveis (para os quais existe um algoritmo) dos indecidíveis (para os quais não existe um algoritmo).
O surgimento dos computadores nas décadas de 30 e 40 aos poucos evidenciou uma diferença entre os problemas decidíveis: muitos parecem ser bem mais difíceis que outros, no sentido de que se conhece apenas algoritmos extremamente lentos para eles. Com isso, surgiu a necessidade de refinar a teoria de computabilidade para tentar explicar essas diferenças. Foi apenas nos anos 60 que a teoria de complexidade, que trata de tais questões, tomou corpo, com a formalização da idéia de "algoritmo eficiente". Foi nessa época que surgiram as definições das classes de complexidade P e NP e do conceito de NP- completude, que captura de certa maneira a dificuldade de se conseguir algoritmos eficientes para certos problemas. Grosseiramente, um problema em NP é dito NP- completo se qualquer outro problema da classe NP pode ser reduzido eficientemente a ele. A mais famosa questão na área de teoria da computação é se P é ou não igual a NP. Se for mostrado que algum problema NP- completo está em P, então tal questão é resolvida e fica provado que P = NP.
Classe de Problemas P, NP e NP-Completo…
É esse o conteúdo que você precisa?
Faça seu login e saiba como ver o trabalho completo
Institucional
Saiba como fazer
Trabalhos Acadêmicos
O Zé Moleza facilita sua vida acadêmica ajudando você em suas pesquisas, e a economizar o seu tempo e o seu dinheiro nos seus trabalhos de faculdade. São mais de 26144 pesquisa acadêmicas entre elas, monografia, temas de monografias, TCC, modelos de monografias, trabalhos de universidades, resenha, Paper, Ensaio, Bibliografia, Trabalhos Escolares.
Dicas de como fazer: Capa de Monografia, capa de TCC, Regras da ABNT, como fazer monografia, como fazer Projeto Final, como fazer seminário, como fazer capas, referências bibliográficas, modelo de monografia.
O Zé Moleza NÃO faz a venda de monografia e É TOTALMENTE CONTRA a compra de monografia pronta e trabalhos prontos. O Zé Moleza NÃO auxilia a quem compra monografia, NÃO apóia a quem quer comprar Trabalhos Prontos, e NÃO APROVA a quem quer comprar TCC prontos, dando dicas de formatação, regras da ABNT, dando sugestões de temas para monografia, resumo de livros, projeto de pesquisa, projeto de mestrado, projeto de pós-graduação, trabalhos acadêmicos, incentivando o usuário a desenvolver por conta própria sua monografia.
