FIND WORDS is the following decision problem:
Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-righ-down. To be specific this is the classic game that can be found in the puzzling week: FIND WORDS
Now this decision problem clearly is in NP because, given a certificate with the positions of the words in the matrix (indexes), a verifier can check it in polynomial time.
My question is this: are we aware of Turing Machines that decide this language in polynomial time?