# Problem: Details, Details, …

Answer the following key questions about the proof of the Cook-Levine theorem that tests our understanding of Turing machines and polynominal-time reductions.

What are the inputs and outputs of the mapping function of the reduction?

Why do the tableaus under consideration have \(n^k\) rows?

Why can we bound the size of the tape,

*i.e.*, the number of columns of the tableau, to \(n^k\)?What do the boolean variables \(x_{i, j, s}\) represent in the reduction?

In a few sentences each, describe the structure and purpose of the following boolean formulae?

- \(\phi_\mathsf{cell}\),
- \(\phi_\mathsf{start}\),
- \(\phi_\mathsf{move}\),
- \(\phi_\mathsf{accept}\)?

Does a \(2 \times 2\) window,

*i.e.*, two rows and two columns, work? Why or why not?How does the constructed boolean function account for the nondeterminism of the NTM it simulates?