Please enable JavaScript.

Coggle requires JavaScript to display documents.

Programas Tratáveis - Coggle Diagram

- - - - Muitos problemas polinomiais que não são de decisão podem ser reduzidos a uma série de problemas de decisão
      - Há problemas de decisão impossíveis de serem resolvidos por algoritmos. Estes são chamados indecisíveis
        
        Os problemas de decisão possíveis, tratáveis ou não, são chamados decisíveis
        
        Há uma quantidade baixa de problemas decisíveis e não tratavéis
      - Uma caracterísitca interessante de problemas de decisão é que apesar de poderem ser difíceis de resolver, checar se uma solução é capaz de resolvê-los é fácil
    - - Aqui estão alguns exemplos providenciados por M. Garey and D. Johnson
        
        Problema do circuito hamiltoniano
        
        Problema do vendedor viajante
        
        Problema da mochila
        
        Problema da partição
        
        Problema da embalagem bin
        
        1 more item...
        
        Esses problemas ou são decisões ou podem ser reescritos como problemas de decisões, mais todos são resolvidos por algoritmos de eficiência exponêncial ou pior
  - - - Gera uma string que pode ser uma possível solução ou lixo inútil
        
        Verifica se a string gerada é uma solução para o problema
        
        Se a string não oferecer uma solução, o algoritmo pode tanto retornar um "não" quanto tentar de novo
        
        Quando essa etapa é feita em tempo polinomial, diz-se que o algoritmo é não-determinísitco polinomial
      - Diz-se que o algoritmo é não-determinístico quando ele consegue acertar o ouput pelo menos uma vez em uma de suas execuções
    - - Esta é a classe dos problemas que podem ser resolvidos por algoritmos não-determinísticos polinomiais
        
        Nela, estão contidos todos os problemas de decisão e os problemas polinomiais
        
        Também está contida nela a maioria dos problemas de decisão, mas não todos. Como exemplificado pelo Halting Problem
        
        Existe a possibilidade das classes P e NP serem, na verdade, a mesma e que os problemas de NP não contidos em P terem soluções que ainda não foram encontradas
        
        Esta é uma pergunta muito importante e que continua sem resposta conclusiva
        
        Ela também pode ser chamada de NP
      - Problemas NP completos
        
        Um problema de decisão é polinomicamente reduzível quando existe uma função computável em tempo polinomial que relacione todas as instâncias "sim" e "não" a todas as instâncias "sim" e "não" de outro
        
        Um problema de decisão é NP completo se pertencer a NP e todo problema de NP for reduzível polinomicamente a ele
        
        Há duas etapas para determinar se um problema é NP completo
        
        Deve-se provar que ele é NP
        
        Uma string gerada aleatóriamente pode ser checada em tempo polinomial para determinar se é ou não solução para o problema
        
        Deve-se provar que todo problema NP é reduzível a ele em tempo polinomial
        
        1 more item...