Exercício 1 - Prova Problema da Cobertura de Vértices é NP-Completo

Поделиться
HTML-код
  • Опубликовано: 21 дек 2024

Комментарии • 11

  • @eliabekun
    @eliabekun 3 года назад +1

    Parabéns pela explicação!

    • @eliabekun
      @eliabekun 3 года назад +1

      Poderia apresentar um algoritmo que resolve esse problema de cobertura de vértices?

    •  3 года назад

      Depois eu vou tentar fazer um vídeo sobre.

  •  4 года назад +1

    A forma correta e formal de como responder o problema se encontra na descrição do vídeo.

    • @JoelsonSousaUFPI
      @JoelsonSousaUFPI Год назад

      Muito bom, parabéns! Somente uma correção (não é bem correção, apenas acho que deveria deixar bem claro esta diferenciação no texto da descrição e NÃO no vídeo): "1º Mostrar que o problema está na classe NP[...]basta apresentar um algoritmo não-determinista que execute em tempo polinomial para resolver o problema. Outra maneira é encontrar um algoritmo determinista polinomial para verificar que uma dada solução é válida". Apresentar esse algoritmo para resolver um problema NP é o que está em aberto hoje, no campo de estudo, o qual nunca foi encontrado, logo a maneira (como falado corretamente no vídeo) mais viável é achar um algoritmo determinista que verifique a solução correta em tempo polinomial.

  • @numseidizer
    @numseidizer 3 года назад

    Muito bom. Mas como foi provado o primeiro problema npc se ainda não tinha sido provado nenhum (para poder fazer o segundo passo)?

    •  3 года назад +1

      Acho que você quis dizer a primeira parte a ida da redução. Se você reduzir uma instância de problema npc ao um outra instância de um outro problema você já provou que o problema que foi reduzido é npc. Porque você achou ele a partir de um npc. Aí a volta é só voltar de novo para o problema noc original.

    • @numseidizer
      @numseidizer 3 года назад +1

      @ oi prof, obrigado por responder. Me expressei mal, perdão. Eu falo em questão do primeiro problema npc encontrado na história lkkkk

    •  3 года назад +1

      @@numseidizer ah sim! O 1º problema a ser provado como um problema NPC foi o SAT. Sua prova foi feita usando a comparação direta com a máquina de Turing que é um dos modelos de computação existentes. Outros exemplos de modelos de computação são algoritmos de Markov e funções recursivas.

    • @numseidizer
      @numseidizer 3 года назад +1

      @ Entendi. Muito top. E se parar para pensar, faz muito sentido o problema de satisfatibilidade ser NPC. Sabendo que um argumento K é válido se, e somente, se ¬K não é satisfazível. Se fosse um problema da classe P, todos os argumentos do universo seriam solucionados, mas, matematicamente, isso é impossível. Muito legal mesmo.

    •  3 года назад

      @@numseidizer exato a pegada é essa. Tudo isso foi possível através da máquina de Turing.