Teoria da Complexidade

Teoria da Complexidade

1. Classes de Problemas

   • Problemas Solucionáveis
     • existe um algoritmo que soluciona o problema
       • entrada com uma resposta afirmativa (ACEITA) ou negativa (REJEITA).
   • Problemas Parcialmente Solucináveis
     • existe um algoritmo capaz de responder SIM
       • São Computáveis
     • Princípio da Redução
       • solucionabilidade de um problema a partir de outro.
         • Reduzir o problema de B, a partir de resoluções feitas em A
   • Problemas Insolucionáveis
     • não existe um algoritmo (Máquina Universal) que solucione o problema
       • Problemas não computáveis
         • Problema da Parada
           • Não existe um algoritmo genérico capaz de verificar se o programa vai parar ou não para a entrada.
             • Loop Infinito
           • Linguagens Recursivamento Enumeráveis
             • Para qualquer cadeia de entrada, se ela fizer parte da linguagem, ou podem funcionar indefinidamente sobre entradas que elas não aceitam (loop)
               • não é possível determinar se aceita ou não a entrada
         • Equivalência de compiladores
           • Não existe algoritmo genérico capaz de comparar quaisquer dois compiladores de LLC e verificar se são equivalentes

2. Complexidade

   • trata da eficiência da computação (dos algoritmos) em computadores existentes.
     • Complexidade temporal
       • tempo de processamento exigido
     • Complexidade espacial
       • espaço de armazenamento exigido
   • Classe de Complexidade
     • um conjunto de funções que podem ser computadas dentro de certos limites de recursos.
       • O conjunto de problemas que podem ser resolvidos por uma máquina abstrata M usando O(f(n)) de recurso R, onde n é o tamanho da entrada.
     • Conjunto dos problemas de decisão
       • Classe P
         • podem ser resolvidos por um algoritmo polinomial.
       • Classe NP
         • dado qualquer instância do problema para a qual a resposta é “sim”, existe um certificado validando este fato
           • pode ser verificado em tempo polinomial.
   • Godel
     • prova que em um sistema lógico formal existem afirmações verdadeiras que não podem ser provadas.
       • Alan Turing
         • Máquina de Turing
           • provas de impossibilidade relacionadas à computação de determinadas tarefas.
             • Indecidibilidade definida
           • o “Problema da Parada” é indecidível

3. Qual é a dificuldade computacional de computar funções?

   • Em 1965, Cobham publica o trabalho
     • teoria que fosse independente de uma máquina
       • definiu e caracterizou uma classe importante de funções que ele chamou de I, i.e
         • números naturais computáveis em tempo limitado por um polinômio no tamanho da entrada.

Images and files in the map