Acessar o Zé Moleza
ou
O que você está pesquisando?
Complexidade de Algoritmos – Problema P versus NP
1151 visualizações
2539 palavras
Adicionar aos favoritos
Loading...- | |
3. Classe NP de Problemas
Problema não-deterministicamente polinomial (NP)?
Um problema não-deterministicamente polinomial é um problema computável cujas soluções até então conhecidas são de ordem exponencial e não se sabe se existe uma solução melhor, de complexidade polinomial.
Observe que o termo "não-determinístico" não implica aleatoridade, mas apenas não se pode afirmar a existência de um algoritmo de complexidade polinomial para o problema em consideração.
Outra observação interessante é que a comprovação de uma solução correta de um problema NP tem complexidade da ordem polinomial,ou seja, a classe NP consiste nos problemas que são verificáveis em tempo polinomial.
Um computador não-determinístico é uma máquina hipotética.
- # infinito de processadores a funcionar em paralelo.
- Se a verificação de uma solução demorar tempo polinomial, então toda a computação demorará tempo polinomial.
Todo problema solúvel em tempo polinomial é verificável em tempo polinomial.
Exemplo:
Problema: Ciclo Hamiltoniano não-direcionado
Dados: Grafo G.
Decisão: G possui um ciclo hamiltoniano?
- Uma justificativa para a resposta SIM pode ser obtida exibindo-se um ciclo C de G e reconhecendo-se…
É 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.
