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 
.
Existence of w is an NP problem since w can be ``guessed''
non-deterministically and verified in P-time.
], where
U is the universal Turing Machine, simulating 
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 
for 
simulate about 
steps
of 
(and, thus, of 
. If the 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 
is reduced to 
by
mapping instances x into 
, with |v| determined by the
time limit for P. Notice that program p for 
is fixed.
So, if some NP problem cannot be solved in P-time then neither
can be the u-problem. Equivalently, if the problem [is there? 
]
IS solvable in P-time then so is any search problem.
We do not know which of these alternatives is true.
It remains to reduce the search problem u to Tiling.
(where 
) by a
TM represented as an array of 1-pointer cellular automata that runs for 
steps and stops if w does NOT solve the predicate P. Otherwise it enters an
infinite loop. An instance x has a solution iff 
runs forever for
some w and 
.
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.
Problem: Find a polynomial time algorithm for n by log n Tiling Problem.