Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 15 - Coggle Diagram

- - - - A redução faz com que possamos dividir algoritmos não-deterministas em menores algoritmos deterministas, afim de resolver um certo problema
      - Um exemplo é o do menor caminho possível entre dois vértices de um grafo:
        
        O problema em si requer uma solução não-determinista, que será um número específico
        
        Para usarmos um algoritmo não-determinista, podemos usar um variável extra k, que auxiliará o processo:
        
        1) Temos um caminho no grafo entre v e u menor que k?
        2) Temos um caminho no grafo entre v e u menor que k-1?
        3) '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' menor que k-2?
        . . .
- - - - Tempo polinomial se refere a eficiência temporal: Ω(cⁿ);
        onde o c é uma constante > 1
  - - - Problemas intratáveis são problemas que, teoricamente, podem ser resolvidos por uma máquina, mas levaria um tempo extremamente longo, devido à sua complexidade, tornando-os impraticáveis
    - - NP-Completo
        
        São uma classe de problemas da classe NP que, se caso um deles for resolvido, todos os outros também poderão ser resolvidos
      - NP-Difícil
        
        São uma classe de problemas que, sendo um problema qualquer de NP, esse pode ser reduzido a um problema X em tempo polinomial
        
        É dito que esse problema X está em NP-Completo se:
        
        Se X está em NP
        
        Se X está em NP-Difícil
        
        A partir disso podemos considerar que: NP-Completo ⊆ NP-Difícil