Please enable JavaScript.

Coggle requires JavaScript to display documents.

Limits to Computation - Coggle Diagram

- - - - Há também problemas no qual não conhecemos se quer solução.
- - - - Quando compramos e/ou escrevemos um programa para resolver um determinado problema e pegamos esse código para resolver um outro problema diferente.
      - Considere 2 problemas para que uma redução adequada de um para o outro possa a ser encontrada.
        
        1º Problem: Nós tomaremos de maneira arbitrária uma instância de input no qual chamaremos de I e transformar I em solução que nós chamaremos SLN.
        
        2º Problema: Tomar uma instância arbitrária de inputs, que chamarei de I' e transformar I' para uma solução que nós chamaremos de SLN'
        
        Nós podemos definir uma redução mais formalmente em 3 passos:
        
        1º Passo: Transformar uma instância I do primeiro proble. para uma instância I' do segundo problema
        
        2º Passo: Aplicar um algoritmo para o segundo problema para a intância I', para fornecer uma solução SLN'.
        
        1 more item...
- - - - Dificuldade de encontrar ou entender um algoritmo para resolver o problema.
    - - Há uma diferença entre programas que rodam em escala polinomial e em escala exponencial.
        
        Na prática, algoritmos polinomias são "viáveis" pois eles tem desempenho razoável com problemas de grandes inputs. Em contrapartida, aos algoritmos exponenciais, que são temporalmente inviáveis com problemas com grandes inputs.
      - Portanto, definiremos que um hard algorithm seja um que rode em tempo exponmencial que Big Omega (c^n) para c > 1.
        
        The Theory of N P-Completenss
        
        non-determinism
        
        É a ideia de "adivinhar" a resposta certa para o problema (ou checar todas as possibilidades de soluções em paralelo para determinar qual delas é a certa).
        
        Algoritmos que trabalham dessa maneira são chamados de non-deterministic algorithm.
        
        Qualquer problema com um algoritmo executado em uma máquina não determinística em tempo polinomial é chamada de NP
        
        Nem todos os probleram que requerem tempo exponencial são NP, pois a non-deterministic machine não pode "adivinhar" e printar a resposta correta.
        
        Problema da NP complete
        
        2 more items...
- - - - Reduzindo o problema conhecido como H ao problema X, significa que estamos usando X como uma etapa para resolver H. Como sabemos que H é hard, logo significa que X também é hard, pois se X não fosse hard H também não seria.
    - - Stephn Cook encontrou um, Grand-daddy.
      - grand-daddy é uma NP-complete que Cook usou-a chamando de SAT.
        
        Cook provou que SAT é NP-Hard.
        
        Entrada 3-SATISFIABILITY (3 SAT):
        Input: Uma expressão booleana E em CNF tal que cada cláusula contém exatamente 3 literais. Output: SIM se a expressão puder ser satisfeita, NÃO caso contrário.
        
        Prove que 3 SAT está em N P: Adivinhe a verdade (não determinística)valores para as variáveis. A exatidão da suposição pode ser verificada em tempo polinomial
        
        Prove that 3 SAT is N P-hard:
        
        Precisamos de uma redução em tempo polinomial
        de SAT a 3 SAT. Seja E = C1 · C2 · ... · Ck qualquer instância de SAT.
        
        Nossa estratégia é substituir qualquer cláusula Ci que não possua exatamente três literais
        com um conjunto de cláusulas, cada uma tendo exatamente três literais.
        
        1 more item...
        
        COBERTURA DO VÉRTEX:
        Input: Um gráfico G e um inteiro k.
        Output: SIM se houver um subconjunto S dos vértices em G de tamanho k ou menos, de modo que cada aresta de G tenha pelo menos um de seus pontos finais em S, e NÃO caso contrário.
        
        Teorema: Cobertura de Vert. são NP-complete.
        
        Prove que VERTEX COVER está em N P: Simplesmente adivinhe um subconjunto do gráfico e determine em tempo polinomial se esse subconjunto é de fato uma cobertura de vértices de tamanho k ou menos.
        
        Prove que VERTEX COVER é N P-difícil: Assumiremos que K-CLIQUE já é conhecido por ser N P-completo.
        
        Dado que K-CLIQUE é N P-completo, precisamos encontrar uma transformação em tempo polinomial da entrada para K CLIQUE até a entrada para VERTEX COVER, e outra transformação em tempo polinomial da saída para
        VERTEX COVER para a saída do K CLIQUE.
        
        1 more item...
- - - - Temos um algoritmo de programação dinâmica cujo custo é Θ(nK) para n objetos cabendo em uma mochila de tamanho K.
        
        Mas acontece que a mochila é NP-completa.
        Isso não é uma contradição?
        
        Não quando consideramos a relação entre n e K. Qual é o tamanho de K?
        
        Tamanho de entrada
        é normalmente O (n lg K) porque os tamanhos dos itens são menores que K.
        
        Assim, Θ (nK) é
        exponencial no tamanho da entrada.
        
        Assim, mesmo que a complexidade do algoritmo de programação dinâmica seja Θ(nK), ela é exponencial em relação ao tamanho real da entrada, O(n lg K). Isso ocorre porque, à medida que "K" aumenta, a complexidade do algoritmo cresce de forma exponencial em relação ao tamanho da entrada.
      - Esse problema é "tratável" se o números são razoáveis.
        
        Tal algoritmo é chamado de algoritmo de tempo pseudo-polinomial.
      - Uma segunda abordagem para manusear problemas de NP-Complete é resolver em instâncias especiais do problema que não são hard.
        
        Exemplo: problemas de VERTEX COVER e K-CLIQUE são NP-Complete, mas há soluções que tem tempo polinominal, como a bipartição dos grafos.
        
        De modo geral, se quisermos garantir que tenhamos a resposta correta para um problema de NP-Complete, precisamos examinar TODAS as possibilidades de solução.
        
        Uma 3º abordagem para resolver é encontrar uma aproximação da solução do problema.
        
        "Um caminho é usar uma heurística para resolver o problema, que é um algoritmo baseado em uma regra prática" no qual nem sempre fornece a melhor resposta.
- - - - Um conju. é chamado contável se todos os membros podem ser associados unicamente a um inteiro positivo.
        
        Um conj. é dito incontável se não é possível associar todos os membros para um conj. próprio de inteiros positivos.
  - - - Começaremos assumindo que a função halt pode resolver o Halting Problem.
        
        A função halt toma dois inputs
        
        Uma string representando
        o código-fonte de um programa ou função
        
        Outra string representando a entrada que desejamos determinar se o programa ou função de entrada ou função halt
        
        A função halt então retorna true se o programa ou função de entrada parar na entrada fornecida, e false caso contrário.
        
        Examinaremos agora duas funções simples que claramente podem existir porque o código completo delas é apresentado aqui
        
        // Return true if "prog" halts when given itself as input
        bool selfhalt(char *prog) {
        if (halt(prog, prog))
        return true;
        else return false;
        }
        
        // Return the reverse of what selfhalt returns on "prog"
        void contrary(char prog) {
        if (selfhalt(prog))
        *while (true); // Go into an infinite loop
        }
        
        O que acontece se fizermos um programa cujo único propósito é executar a função contrária e executar esse programa tendo ele mesmo como entrada? Uma possibilidade é que a chamada para selfhalt retorne verdadeira; isto é, selfhalt afirma que o contrário irá parar quando executado sobre si mesmo. Nesse caso, o contrário entra em um loop infinito (e, portanto, não para). Por outro lado, se selfhalt retorna falso, então halt está proclamando que o contrário não para em si mesmo, e o contrário então retorna, isto é, ele para. Assim, o contrário faz o contrário daquilo que halt diz que fará.
        
        A ação contrária é logicamente inconsistente com a suposição de que halt resolve o problema da parada corretamente. Não há outras suposições que possamos feito que possa causar essa inconsistência. Assim, por contradição, provamos que a parada não pode resolver o problema da halt corretamente e, portanto, não há programa que pode resolver o problema da parada.