Trova le parole in p?

Question

TROVARE LE PAROLE è il seguente problema di decisione:

Dato un elenco di parole L e una matrice M, sono tutte parole in L anche in M? Le parole in M Può essere scritto fino a giù, giù verso l'alto, da sinistra a destra, da destra a sinistra, diagonale-sinistra-up, diagonale-sinistra-giù, diagonale-in-right-up e diagonale-rull-giù. Per essere specifico, questo è il gioco classico che può essere trovato nella settimana sconcertante: TROVARE LE PAROLE

Ora questo problema decisionale è chiaramente in NpPerché, dato un certificato con le posizioni delle parole nella matrice (indici), un verificatore può controllarlo in tempo polinomiale.

La mia domanda è questa: siamo a conoscenza delle macchine Turing che decidono questa lingua in tempo polinomiale?