\newpage\subsection{An NP-Complete Problem: Tiling.\label{tile}}

\parbox{5in} {{\bf Example: NP-complete Tiling Problem.} Invert the function
which, given a tiled square, outputs its first row and the list of tiles used.
A tile is one of the $26^4$ possible squares containing a Latin letter at each
corner. Two tiles may be placed next to each other if the letters on the mutual
side are the same. E.g.:} \hspace{2pc} \parbox{6pc} {\mbox
 {\fbox{\parbox{2pc} {\makebox[2pc] {a\hfill x} \makebox[2pc] {m\hfill r}}}
  \fbox{\parbox{2pc} {\makebox[2pc] {x\hfill c} \makebox[2pc] {r\hfill z}}}}
  \par \vspace {3pt} \mbox
 {\fbox{\parbox{2pc} {\makebox[2pc] {m\hfill r} \makebox[2pc] {n\hfill s}}}
  \fbox{\parbox{2pc} {\makebox[2pc] {r\hfill z} \makebox[2pc] {s\hfill z}}}}}

We now reduce any NP/search problem $P$ to Tiling. Recall: A search problem is,
given $x$, to find $w$ which satisfies a P-time computable property $P(x,w)$.
Existence of $w$ is an NP problem since $w$ can be ``guessed''
non-deterministically and verified in P-time.

\paragraph {Padding Argument.} First, we need to reduce it to some ``standard''
NP problem. An obvious candidate is the problem [Is there? $w: U(v,w)$], where
$U$ is the universal Turing Machine, simulating $P(x,w)$ for $v = px$.
 A difficulty is that $U$ does not run in P-time. We must restrict $U$
to $u$ which stops within some P-time limit. How to make this fixed
degree limit sufficient for simulating any polynomial (even of higher degree)
time $P$? Let the TM $u(v,w)$ for $v=00\ldots01px$ simulate about $|v|^2$ steps
of $U(px,w)$ (and, thus, of $P(x,w))$. If the {\em padding} of $0$'s in $v$ is
sufficiently long, $u$ will have enough time to simulate $P$, even though $u$
runs in quadratic time, while $P$'s time limit may be, say, cube (of a shorter
``un-padded'' string). So the NP problem $P(x,w)$ is reduced to $u(v,w)$ by
mapping instances $x$ into $f(x)= 0\ldots01px=v$, with $|v|$ determined by the
time limit for $P$. Notice that program $p$ for $P(x,w)$ is fixed.

So, if some NP problem {\em cannot} be solved in P-time then neither
can be the $u$-problem. Equivalently, if the problem [is there? $w: u(v,w)$]
{\em IS} solvable in P-time then so is {\em any} search problem.
 We do not know which of these alternatives is true.
 It remains to reduce the search problem $u$ to Tiling.

\paragraph{The Reduction.} We compute $u(v,w)$ (where $v = 00\ldots01px$) by a
TM represented as an array of 1-pointer cellular automata that runs for $|v|^2$
steps and stops if $w$ does NOT solve the predicate $P$. Otherwise it enters an
infinite loop. An instance $x$ has a solution iff $u(v,w)$ runs forever for
some $w$ and $v = 0\ldots01px$.

\noindent \parbox{297pt} {Here is the space-time diagram of computation of
$u(v,w)$. We set $n$ to $u$'s time (and space) $|v|^2$. Each row in this table
represents the configuration of $u$ in a different moment of time. The solution
$w$ is filled in at the second step below a special symbol "?". Suppose
somebody fills in a wrong table that doesn't reflect the actual computation. We
claim that any wrong table has four adjacent squares that couldn't possibly
appear in the computation of $u$ on any input.} \hspace{1pc}
 \parbox{13pc} {\vector(1,0){89}~space:~$n=|v|^2$\\\mbox
 {\raisebox{3pc}{\vector(0,-1){50}}\hspace{-10pt}\raisebox{-2pc}{time} \fbox
 {\parbox{11pc}{\makebox[11pc]{$v$ ?\ldots? \#\ldots\#\hfill(init.config.)}
\makebox[11pc]{\makebox[2pc]{$v$\hfill$w$}\hfill $T_1$\hfill\makebox[2pc]{}}
 \makebox[11pc]{\vdots\hfill\vdots\hfill\vdots} \makebox[11pc]{$T_n$}}}}}

 \paragraph {Proof.} As the input $v$ and the guessed solution $w$ are the same
in both the right and the wrong tables, the first 2 lines agree. The actual
computation starts on the third line. Obviously, in the first mismatching line
a transition of some cell from the previous line is wrong. This is visible from
the state in both lines of this cell and the cell it points to, resulting in an
impossible combination of four adjacent squares.

\noindent\parbox{383pt} {\hspace*{1pc} For a given $x$, the existence of $w$
satisfying $P(x,w)$ is equivalent to the existence of a table with the
prescribed first row, no halting state, and permissible patterns of each four
adjacent squares. Conversion of our table to the {\em Tiling Problem}:\\ The
squares in the table are separated by ``---'' ; the tiles by ``...''; Break
every square in the table into 4 parts, each part represents a corner of 4
separate tiles. If the 4 adjacent squares in the table are permissible, then
the square is also tiled permissibly.} \hspace{2pc}
 \(\raisebox{-18pt}{\dashbox{1}(40,40){\parbox{2.5pc}
 {\makebox[2.5pc]{u\hfill v}\\\hspace*{2.5pc}\\\makebox[2.5pc]{v\hfill x}}}}
\hspace{-57pt}\parbox{75pt} {\framebox[3pc]{\rule{0pt}{2pc}}
\framebox[3pc]{\rule{0pt}{2pc}}\vspace{3pt} \framebox[3pc]{\rule{0pt}{2pc}}
\framebox[3pc]{\rule{0pt}{2pc}}}\)

 \vspace{6pt} So, any P-time algorithm extending a given first line to the
whole table of matching tiles from a given set would solve all NP problems by
converting them to Tiling as shown.

\paragraph {Problem:} Find a polynomial time algorithm for $n\times \log
n$ Tiling Problem.