Please enable JavaScript.

Coggle requires JavaScript to display documents.

Limites da Computação - Coggle Diagram

- - - - Algoritmo não determinístico que roda em tempo polinomial em uma máquina não determinística (problema NP)
    - - Se um problema NP-Completo tiver uma solução que funcione em tempo polinomial, todos os problemas NP-Completo devem ser capazes de ter uma solução em um tempo polinomial
  - - - Se H é NP-Completo, X também é NP-Completo
- - - - O conjunto das funções que podem ser descritas por um computador pode ser visto como uma sequência de caracteres da tabela ASCII
        
        O conjunto de elementos usados dentro de um programa é um conjunto contável, logo todas as strings de um programa podem ser designadas a um elemento do conjunto
      - O conjunto das funções possíveis é um conjunto incontável, a partir de uma função F(x) é possível descrever uma função F2(x) tal que F2(x) = F(x) + 1, criando uma função que ainda não havia sido mapeada no conjunto
        
        A criação de elementos que não haviam sido mapeados por meio de elementos mapeados anteriormente caracteriza a criação de conjuntos infinitos não contáveis
        
        Dessa forma, o conjunto das funções possíveis é um conjunto incontável