Please enable JavaScript.

Coggle requires JavaScript to display documents.

P, NP e NP-Complete Problems - Coggle Diagram

- - - - Complexidade computacional: classifica os problemas de acordo com sua dificuldade inerente.
        
        Conjunto P: problemas resolvidos com tempo polinomial. Uma definição mais formal inclui P em problemas de decisão, ou seja, problemas que possuem como resposta "sim" ou "não".
        
        DEFINIÇÃO 2: Classe P é a classe de problemas de decisão que podem ser resolvidos em tempo polinomial por algoritmos determinísticos.
        
        A restrição de P para problemas de decisão se dá pelos seguintes motivos:
        1- Saídas grandes (exemplo: gerar subconjuntos de um dado conjunto);
        2- Problemas importantes que não são de decisão podem ser adaptados para uma série de problemas de decisão mais fáceis de estudar (exemplo: número mínimo de cores necessárias para colorir vértices de um grafo para que não haja dois vértices adjacentes da mesma cor);
        
        No exemplo do item 2, poderíamos simplesmente perguntar se existe uma coloração dos vértices do grafo com não mais de m cores.
        
        Nem todo problema de decisão pode ser resolvido em tempo polinomial.
        
        Problemas decidíveis: podem ser resolvidos por um algoritmo;
        Problemas indecidíveis: não podem ser resolvidos por um algoritmo.
        
        1 more item...