Please enable JavaScript.

Coggle requires JavaScript to display documents.

LIMITS TO COMPUTATION - Coggle Diagram

- - - - uma cláusula é um ou mais literais combinados com OU
        
        Forma Normal Conjuntiva (CNF) é uma expressão booleana escrita como uma série de cláusulas combinadas com E
        
        Cook provou que SAT é NP-Difícil
        
        qualquer problema de decisão que pode ser executado pela máquina de Turing é transformável em SAT, assim SAT é NP-Difícil
  - - - o número de funções inteiros é incontável.
- - - - não existe um algoritmo de tempo O(n) para emparelhamento. emparelhamento deve ser pelo menos tão caro quanto ordenação
        
        a redução nos dá uma maneira de entender os limites de um problema em termos de outro
- - - - problemas são aqueles problemas que podem ser resolvidos em tempo polinomial em uma máquina não-determinística
        
        um problema de decisão é simplesmente aquele cuja resposta é sim ou não
        
        NP-Difícil: se qualquer problema em NP puder ser reduzido a x em tempo polinomial
        
        NP-Completo: um problema x é definido como NP-Completo se x está em NP e x é NP-Difícil
        
        problemas que são solucionáveis em tempo polinomial em um computador regular são ditos estar na classe P