Leia o texto a seguir: 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 de decisão Sudoku é um problema categorizado como NP, o qual é um conjunto da classe P.
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 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.
O problema do jogo Sudoku está na classe de algoritmos Polinomiais, logo, são chamados de eficientes.