Please enable JavaScript.

Coggle requires JavaScript to display documents.

Limites da Computação - Coggle Diagram

- - - - Classe de problemas para os quais é fácil verificar uma solução, mas pode ser extremamente difícil encontrar uma.
        
        Problema do Caixeiro Viajante (PCV): Dado um conjunto de cidades e as distâncias entre cada par de cidades, o problema consiste em encontrar a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade de origem.
        
        Problema da Satisfatibilidade Booleana (SAT): Dado uma expressão booleana em forma normal conjuntiva (FNC), o problema consiste em determinar se existe uma atribuição de valores verdade para as variáveis que faça a expressão ser verdadeira.
    - - Método para demonstrar que um problema é NP-Completo através da redução de um problema já conhecido como NP-Completo para este.
        
        Redução de SAT para 3-SAT: Uma forma comum de provar que um problema é NP-completo é reduzi-lo a partir de um problema já conhecido como NP-completo, como o SAT. Por exemplo, qualquer problema de SAT pode ser transformado em um problema de 3-SAT (uma variante do SAT onde cada cláusula tem exatamente três literais), demonstrando assim a NP-completude do 3-SAT.
      - Redução do PCV para Subconjunto-Soma: Um exemplo hipotético, mostrando que técnicas de redução podem ser usadas para mostrar a dificuldade de problemas aparentemente não relacionados, ao encontrar maneiras de traduzir a solução de um problema (como o PCV) para resolver outro (como Subconjunto-Soma).
    - - Estratégias para lidar com problemas NP-Completos, incluindo algoritmos aproximados, heurísticas e soluções parciais.
        
        Heurísticas: Algoritmos que não garantem a solução ótima, mas podem encontrar soluções boas em tempo prático. Exemplo: Algoritmo de aproximação para o PCV.
        
        Algoritmos de Aproximação: Específicos para problemas onde uma solução "próxima" é aceitável. Exemplo: Algoritmo para o problema da cobertura de conjuntos que encontra uma solução dentro de um fator logarítmico do ótimo.
        
        Algoritmos de Backtracking e Branch-and-Bound: Usados para explorar sistematicamente todas as possíveis configurações para encontrar a solução exata. Exemplo: Solucionadores de SAT que usam backtracking.
- - - - A incontabilidade é um conceito na teoria da computação que indica que existem mais problemas do que podemos resolver com nossos computadores, no sentido de que não há como contar ou enumerar todos os problemas possíveis devido à sua infinitude. Isso é ilustrado pela diagonalização de Cantor, que mostra que nem todos os conjuntos infinitos têm o mesmo tamanho ou cardinalidade, especialmente destacando que o conjunto de todos os programas de computador é contável, mas o conjunto de todas as funções possíveis é incontável.
    - - O Problema da Parada, proposto por Alan Turing, pergunta se é possível criar um algoritmo que, dado qualquer programa de computador e uma entrada para esse programa, determinará corretamente se o programa termina (ou "para") ou continuará a executar indefinidamente. Turing provou que tal algoritmo é impossível de ser criado, o que estabelece um limite fundamental sobre o que é computável. A prova de Turing usa o argumento da diagonalização para mostrar que, se tal algoritmo existisse, poderia ser usado para criar um programa que, quando alimentado com sua própria descrição, levaria a uma contradição lógica. Isso mostra que existem problemas bem definidos que são impossíveis de resolver usando algoritmos, destacando um limite fundamental da computação.
- - - - SAT para 3-SAT: Uma redução clássica é transformar uma instância geral do Problema da Satisfatibilidade (SAT) em uma instância do 3-SAT, onde cada cláusula tem exatamente três literais. Isso é feito através da introdução de variáveis extras e cláusulas adicionais para dividir cláusulas maiores em várias cláusulas de três literais, sem alterar a satisfatibilidade da fórmula original.
      - 3-SAT para Problema do Clique: Outro exemplo é a redução do 3-SAT para o Problema do Clique, demonstrando que encontrar um clique de tamanho k em um grafo (um subconjunto de k vértices todos conectados entre si) é tão difícil quanto resolver uma instância do 3-SAT.