Please enable JavaScript.

Coggle requires JavaScript to display documents.

Problemas P, NP e NP-completo - Coggle Diagram

- - - - Resposta sim ou não
      - Nem todos os problemas de decisão podem ser resolvidos em tempo polinomial
        
        Problemas não-determináveis
      - Checar se uma hipótese de solução resolve o problema é fácil
    - - Exemplos
        
        Problema do circuito Hamiltoniano
        
        Problema do vendedor viajante
        
        Problema do particionamento
      - O número de possibilidades aumenta de forma exponencial de acordo com o tamanho da entrada
    - - Procedimento de 2 fases
        
        Fase não-determinística ("Fase do chute")
        
        Uma string S arbitrária é gerada como possível solução para a instância I do problema
        
        Fase determinística ("Fase de verificação")
        
        Utiliza I como entrada e S como saída para verificar se S é uma solução
      - Resolve um problema se, e somente se, para cada instância correta do problema ele retorna correto em alguma execução
      - Não-determinístico polinomial se a eficiência temporal da fase de verificação é polinomial