Mind map
Problemas Classe P
Map content
Problemas Classe P
Solucionáveis em Tempo Polinomial
- Maquina de Turing
- Tempo de execução = O(n^k), k constante.
Verificador de tempo polinomial
- Problema Classe NP
- Intratabilidade
- Não solucionáveis em tempo polinomial
- NP-Completo
- P⊆NP
- Se um NP for solucionável, todos os outros também são.
- Mostra-se o limite inferior
- Problemas de decisão
- NP-Hard
- Tão difíceis quanto os mais difíceis de NP
- A não ser que P = NP.
- Tão difíceis quanto os mais difíceis de NP
- Intratabilidade
- Problema Classe NP
Tratabilidade
Information
- Description
- Computação Mind Map on Problemas Classe P, created by Leonardo Torres on 06/12/2020.
- Created by
- Leonardo Torres
- Views
- 0
- Rating