FIND WORDS It is the following decision problem:
Given a list of words L and a matrix SUBWAY, are all the words in L Also in SUBWAY?
The words in SUBWAY can be written from top to bottom, from bottom to top, from left to right, from right to left, diagonal to left, diagonal to left, diagonal to right and diagonal to right.
To be specific, this is the classic game that can be found in the week of the puzzles: FIND WORDS
Now, this decision problem is clearly in public notary
because, given a certificate with the positions of the words in the matrix (indexes), a verifier can verify it in polynomial time.
My question is this: do we know the Turing machines that decide this language in polynomial time?