16

Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, for a total of $O(n^2)$ possible placements. Checking each one costs at most $O(m)$, where $m$ is the length of the word. In total, we obtain an algorithm whose ...


5

Let $M$ be a $n \times n$ matrix. And I am searching a word $l_ll_2 \dots l_k $ of length $k$. Now first we search $l_1$ in $M$. It takes $O(n^2)$ time. For each successful search, we look at all eight direction (up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-right-down) and check ...


2

The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all. In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, ...


1

As I understand it, you are interpreting the space $\{ 0,1 \}^\ast$ to be the (disjoint) union of $F$ and $\overline{F}$, where $F$ is the set of valid formulas and $\overline{F}$ is the set of strings which do not encode a formula (according to some unspecified encoding). Then, in your perspective, we should have that $F = \textsf{SAT} \cup \overline{\...


Only top voted, non community-wiki answers of a minimum length are eligible