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.
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.
@ 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.
@ 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.
Parabéns pela explicação!
Poderia apresentar um algoritmo que resolve esse problema de cobertura de vértices?
Depois eu vou tentar fazer um vídeo sobre.
A forma correta e formal de como responder o problema se encontra na descrição do vídeo.
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.
Muito bom. Mas como foi provado o primeiro problema npc se ainda não tinha sido provado nenhum (para poder fazer o segundo passo)?
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.
@ oi prof, obrigado por responder. Me expressei mal, perdão. Eu falo em questão do primeiro problema npc encontrado na história lkkkk
@@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.
@ 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.
@@numseidizer exato a pegada é essa. Tudo isso foi possível através da máquina de Turing.