est-ce que des mots sont en p?

Question

TROUVER LES MOTS est le problème de décision suivant:

Étant donné une liste de mots L Et une matrice M, sont tous des mots dans L aussi dans M? Les mots dans M Peut être écrit jusqu'au bas, vers le haut, de gauche à droite, de droite à gauche, diagonal-gauche, diagonal-gauche, diagonal-droite et diagonal-righ-down. Pour être spécifique, c'est le jeu classique que l'on trouve dans la semaine déroutante: TROUVER LES MOTS

Maintenant, ce problème de décision est clairement dans NPParce que, étant donné un certificat avec les positions des mots dans la matrice (index), un vérificateur peut le vérifier en temps polynomial.

Ma question est la suivante: sommes-nous conscients des machines Turing qui décident de cette langue en temps polynomial?