Mindmap

Problemas Classe P

Leonardo Torres Computação Portugiesisch

Inhalt der Mindmap

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

Beschreibung: Computação Mindmap am Problemas Classe P, erstellt von Leonardo Torres am 06/12/2020.
Erstellt von: Leonardo Torres
Aufrufe: 0
Bewertung