Next: 5 Randomness in Computing. Up: 4 Nondeterminism; Inverting Functions; Previous: 4.2 Complexity of NP

## 4.3 An NP-Complete Problem: Tiling.

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.

First, we need to reduce it to some ``standard'' NP problem. An obvious candidate is the problem [Is there? ], 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.

#### The Reduction.

We compute (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 .

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

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.

Next: 5 Randomness in Computing. Up: 4 Nondeterminism; Inverting Functions; Previous: 4.2 Complexity of NP

Leonid Levin
Wed Aug 21 20:35:42 EDT 1996