Dada uma grade de Sudoku incompleta (famoso jogo baseado na colocação lógica de números), desejamos saber se ela possui pelo menos uma solução váli...
Dada uma grade de Sudoku incompleta (famoso jogo baseado na colocação
lógica de números), desejamos saber se ela possui pelo menos uma solução
válida. Qualquer solução de Sudoku proposta pode ser facilmente verificada, e o
tempo para verificar uma solução cresce de forma polinomial à medida que a
grade aumenta.
Qual propriedade melhor descreve a solução dessa classe de problema?
O problema de decisão Sudoku está em NP se suas soluções podem ser verificadas de forma eficiente.
O problema do jogo Sudoku está na classe NP, logo, também é da classe P, uma vez que NP é uma classe de problemas dentro de P.
O problema de decisão Sudoku é um problema categorizado como NP, o qual é um conjunto da classe P.
O problema do jogo Sudoku está na classe de algoritmos Polinomiais, logo, são chamados de eficientes.
O Sudoku é resolvido em um tempo P, onde P é o conjunto de todos os problemas de decisão que são solucionáveis com eficiência.
lógica de números), desejamos saber se ela possui pelo menos uma solução
válida. Qualquer solução de Sudoku proposta pode ser facilmente verificada, e o
tempo para verificar uma solução cresce de forma polinomial à medida que a
grade aumenta.
Qual propriedade melhor descreve a solução dessa classe de problema?
O problema de decisão Sudoku está em NP se suas soluções podem ser verificadas de forma eficiente.
O problema do jogo Sudoku está na classe NP, logo, também é da classe P, uma vez que NP é uma classe de problemas dentro de P.
O problema de decisão Sudoku é um problema categorizado como NP, o qual é um conjunto da classe P.
O problema do jogo Sudoku está na classe de algoritmos Polinomiais, logo, são chamados de eficientes.
O Sudoku é resolvido em um tempo P, onde P é o conjunto de todos os problemas de decisão que são solucionáveis com eficiência.
💡 1 Resposta
Ed 
A propriedade que melhor descreve a solução dessa classe de problema é: "O problema de decisão Sudoku está em NP se suas soluções podem ser verificadas de forma eficiente." Isso significa que, embora encontrar uma solução para o Sudoku possa ser difícil, verificar se uma solução proposta é válida é relativamente fácil e pode ser feito em tempo polinomial. Portanto, o problema de decisão Sudoku está na classe NP (problemas que podem ser verificados em tempo polinomial), mas não se sabe se está na classe P (problemas que podem ser resolvidos em tempo polinomial).
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Compartilhar