\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.