Mapa mental

Problemas Classe P

Leonardo Torres Computação Português

Conteúdo do mapa

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.
Tratabilidade

Descrição: Computação Mapa Mental sobre Problemas Classe P, criado por Leonardo Torres em 06-12-2020.
Criado por: Leonardo Torres
Visualizações: 0
Avaliação