Please enable JavaScript.

Coggle requires JavaScript to display documents.

Problemas P, NP e NP-Completo - Coggle Diagram

- - - - Enorme diferença na eficiência temporal
        
        Pouquíssimos algoritmos úteis com o grau maior que 3.
    - - Soma
      - Composição
    - - Complexidade computacional
        
        Classifica os problemas de acordo com sua dificuldade inerente
- - - - Problemas importantes podem ser resolvidos em tempo polinomial
      - Vários problemas podem ser reduzidos a uma série de problemas de decisão
  - - - Se um problema está em P podemos usar o algoritmo de tempo polinomial determinístico que resolve no estágio de verificação de um algoritmo não determinístico
    - - Proplema de decisão que não está em NP
        
        Gera questão em aberto da ciência da computação
        
        P é um subconjuto próprio de NP ou essas 2 classes são iguais?
- - - - Alguns problemas de decisão não podem ser resolvidos por nenhum algoritmo
    - - Problemas de decisão que podem ser resolvidos por algum algoritmo
  - - - Dado um programa de computador e uma entrada, determina-se se o programa irá parar nessa entrada ou continuará trabalhando no problema
    - - Determinar se um grafo tem circuito hamiltoniano
        
        Caminho que começa e termina no mesmo vértice e passa por todos os outros vértices exatamente uma vez
    - - Encontrar o passeio mais curto por n cidades com distâncias inteiras e positivas
        
        Encontre o caminho hamiltoniano mais curto em um grafo completo com pesos inteiros e positivos
    - - Encontre o subconjunto mais valioso de itens de pesos inteiros e positivos e valores que cabem em uma mochila de capacidade inteira e positiva
    - - Dado n inteiros positivos determinar se é possível particionar em 2 subconjuntos disjuntos com mesma soma
    - - Dado n itens cujo tamanhos são números racionais positivos não maiores que 1, colocar no menor número de escaninhos de tamanho 1
    - - Encontrar o número cromático de um grafo
        
        Menor número de cores para colorir todos os vértices de um grafo de forma que 2 vértices adjacentes não tenham a mesma cor
    - - Encontre o máximo (ou mínimo) valor de uma função linear de várias variáveis de valor inteiro sujeitas a um conjunto de restrições
  - - - Toma como entrada uma instância I de um problema e faz
        
        Adivinhação
        
        Estágio não determinístico
        
        Uma string arbitrária S é gerada e pode ser considerada uma solução para a instância I
        
        Verificação
        
        Estágio Determinístico
        
        Leva I e S como sua entrada e a saída é sim se S for solução para uma instância I
    - - O algoritmo deve ser capaz de adivinhar a solução pelo menos uma vez e possa verificar sua validade
        
        Não pode produzir reposta sim em instância que a resposta deve ser não
    - - Eficiência do estágio de verificação é polinomial
- - - - O problema D1 pode ser também em tempo polinomial