\documentclass{article}
\include{18313-preamble}
\usepackage{graphicx}

\begin{document}
\lecture{2004/02/25}{Dan Ports}{2004/03/03}{drkp@mit.edu}
\lecturetitle{Tetris is Hard, Even to Approximate}{Erik D. Demaine,
  Susan Hohenberger, and David Liben-Nowell, Technical Report
  MIT-LCS-TR-865, Massachusetts Institute of Technology, October 21,
  2002}{Dan Ports}{Dan Ports}

\section{\emph{Tetris}: the game}

Tetris is a famous computer game in which falling blocks are placed on
a grid. The gameboard is a $m$ by $n$ rectangular grid (typically
approximately 20 rows by 10 columns). In the version that we consider,
the gameboard initially has some of its squares filled.

\begin{figure}[hbp]
  \centering
  \includegraphics[scale=.5]{tetrominoes}
  \caption{The seven tetrominoes: ``square'' (\textsf{Sq}), ``left
    gun'' (\textsf{LG}), ``right gun'' (\textsf{RG}), ``left snake''
    (\textsf{LS}), ``right snake'' (\textsf{RS}), ``I'' (\textsf{I}),
    and ``T'' (\textsf{T}). Centers of rotation are marked. (Demaine et
    al., p. 2)}
  \label{fig:tetrominoes}
\end{figure}

A sequence of pieces, known as \emph{tetrominoes}, fall and are placed
by the player into the grid. The seven tetrominoes are shown in
Figure~\ref{fig:tetrominoes}\footnote{All figures are taken from the
  referenced paper Erik D. Demaine, Susan Hohenberger, and David
  Liben-Nowell, \emph{Tetris is Hard, Even to Approximate}, Technical
  Report MIT-LCS-TR-865, Massachusetts Institute of Technology,
  October 21, 2002. Used without permission.}. A new piece appears in
the top of the gameboard, and begins falling. The player can move the
piece left and right, and rotate it clockwise or counter-clockwise in
90-degree increments. When the bottom of the falling piece touches
another piece, it is fixed in place and the next piece appears. We
consider the full-information version of the game in which the player
knows in advance the finite, deterministic sequence in which the
pieces will appear. This variant is much easier to analyze, and it
seems intuitive that the partial-information, ``online'', version will
only be harder.

Whenever a row is filled completely, that row is \emph{cleared}:
removed from the gameboard. All pieces above it are shifted down one
row (and only one row --- pieces do not slide down more than one row,
even if there is space available below). If the board fills up such
that the next piece's initial position is blocked, the game ends with
the player losing. Though the piece sequence is finite in the variant
we consider, in a typical Tetris game, the game continues until the
player loses. Thus, the goal is to place the pieces in such a way that
they mesh together and clear rows.


\section{\textsc{Tetris}: the problem}
We now formalize the game of Tetris slightly and express it as a
problem whose complexity can be analyzed. We define a \emph{game}
$\mathcal{G}$ to be an initial board state $B$ and a set of pieces
$P_0 \ldots P_p$:
\[ \mathcal{G}= \langle B, P_0, \ldots, P_p \rangle \]

We then define a \emph{trajectory sequence} $\Sigma$ to be a sequence
of \emph{moves} for each of the pieces. We are only interested in
\emph{acyclic} trajectory sequences, i.e. ones where the same state is
never reached more than once. There are six possible moves:
\begin{enumerate}
\item Drop the current piece one row
\item Slide the current piece to the left one column
\item Slide the current piece to the right one column
\item Rotate the current piece $90^\circ$ clockwise around its center
\item Rotate the current piece $90^\circ$ counterclockwise around its
  center
\item Fix the current piece in place and drop the next piece (assuming
  the current piece cannot drop further) 
\end{enumerate}
(To make this an algorithmic problem, we ignore the timing aspects of
the game --- we assume the player is dropping the pieces, rather than
the pieces automatically falling.)

\paragraph{}

We now define the problem
\textsc{Tetris-$k$-cleared-rows}$\left[\mathcal{G},\Sigma\right]$:

\paragraph{Given:} A game $\mathcal{G}$
and integer $k$,

\paragraph{Output:} Does there exist an acyclic trajectory sequence $\Sigma$
that can be applied to $\mathcal{G}$ such that $k$ rows are cleared?

\paragraph{}

We will show that \textsc{Tetris-$k$-cleared-rows} is
$\NP$-complete. To begin with, we show that it is in $\NP$.

\begin{theorem}
  \textsc{Tetris-$k$-cleared-rows} is in $\NP$.
\end{theorem}

\begin{proof}
  Given an acyclic trajectory sequence $\Sigma$, we can confirm that
  all moves in $\Sigma$ are legal in time polynomial in $\Sigma$.

  We note that $\abs{\Sigma}$ is polynomial in the size of
  $\mathcal{G}$. Since $\Sigma$ is acyclic, there can be at most
  $p\left(4\abs{B}+1\right)$ states: each piece placed in each
  position of the gameboard in each orientation, plus the final fixed
  state of each piece. So we can verify in time polynomial in
  $\mathcal{G}$ the number of rows cleared by $\Sigma$.
\end{proof}

Though we consider first the problem of whether it is possible to
clear $k$ rows in the given game, it seems natural that this problem
should be equivalent in difficulty to several other objectives, such
as maximizing the number of played pieces. This is, in fact, the case:
these different objectives require only a slight modification to the
reduction.



\section{The 3-Partition problem}
\label{sec:3partition}

To prove the $\NP$-completeness of \textsc{Tetris-$k$-cleared-rows},
we will reduce the $\NP$-complete problem \textsc{3-Partition} to it.
The \textsc{3-Partition} problem is defined as follows:

\paragraph{Given:}
A sequence  of positive integers and a
positive integer $T$, with each $a_i$ strictly between $\frac{T}{4}$
and $\frac{T}{2}$ and satisfying $\sum_i a_i = sT$
\paragraph{Output:}
Can $\{a_1,\ldots, a_{3s}\}$ be partitioned into $s$ disjoint subsets
$\{A_1,\ldots,A_s\}$ such that for all $j$,
$\sum_{a_i\in A_j} = T$?

\paragraph{}

This problem has been proven to be $\NP$-complete in the strong
sense: it is $\NP$-complete even if the inputs are provided in unary
(which is fortunate, since this is essentially what we will do!)

We impose three technical conditions on instances of
\textsc{3-Partition} to aid in our reduction. We consider only
instances that satisfy the following:
\begin{enumerate}
\item $T$ is even
\item For any set $S \subset \left\{a_1,\ldots,a_{3s}\right\}$ with
  $\sum_{a_i\in S} a_i = T$, $\abs{S} = 3$
\item If $\sum_{a_i \in A_j} a_i \neq T$, then $\abs{T- \sum_{a_i \in
      A_j} a_i} \ge 3s$
\end{enumerate}

However, these three conditions are, in fact, not very restrictive: we
can make any \textsc{3-Partition} instance satisfy these conditions by
multiplying each of the $a_i$'s and $T$ by $4s$. This clearly ensures
that the first property holds. The second follows from the condition
that $\frac{T}{4} < a_i < \frac{T}{2}$, which continues to hold. For
the third, note that if $\sum_{a_i \in A_j} a_i \neq T$, then the
difference is at least 1 since the values are all integers; thus,
multiplying by $4s$ multiplies the difference, giving the third
condition.



\section{The reduction}
\label{sec:reduction}

We now define a reduction from an arbitrary instance of
\textsc{3-Partition} satisfying our constraints above to an instance
of \textsc{Tetris-$k$-cleared-rows}. That is, given a
\textsc{3-Partition} instance $\mathcal{P} = \langle a_1, \ldots,
a_{3s}, T\rangle$, we will find a Tetris game $\mathcal{G(P)}$ in
which the maximum number of rows can be cleared if and only if a
3-partitioning of $\mathcal{P}$ is possible.

Essentially, we will encode the value $T$ in the gameboard and the
values $a_i$ in the piece sequence. The piece sequence will consist of
a series of groups of pieces that represent each of the $a_i$'s in
unary: the longer the group, the larger the value of $a_i$. The
gameboard will be arranged into $s$ vertical buckets of height
proportional to $T$. The pieces are selected such that all of the
pieces representing the same integer $a_i$ must be placed in the same
bucket. On this board, rows cannot be cleared until all buckets are
filled. Thus, the only way to clear the maximum number of rows is to
fill the buckets. But each of the $s$ buckets has height proportional
to $T$, so they can only be filled if there are $s$ subsets of the
$a_i$'s that sum to $T$.

More precisely, we define an initial gameboard $B_0$ that has $6s +3$
columns, and $6T+22$ rows containing pieces. In addition, there are
another $3s+O(1)$ empty rows used only for rotation; having so many
rows available means that we can severely restrict the amount of
rotation permitted. The exact number of rows required depends on the
specific details of the rotation model in use. However, neglecting
this constraint, we do not require so much space. Regardless, we do
not place pieces above the $6T+22$nd row, so we refer to this as the
``highest'' row.

\begin{figure}[htpb]
  \centering
  \includegraphics[scale=.5]{gameboard}
  \caption{The reduction's gameboard. (Demaine et al, p. 8)}
  \label{fig:gameboard}
\end{figure}

The filled portion of the gameboard is divided into $s$ buckets of six
columns each, plus a three-column lock on the right, as in
Figure~\ref{fig:gameboard}. The columns of
each bucket can be described as follows:
\begin{itemize}
\item The first and second columns are empty except for the first four
  rows.
\item The third column is empty.
\item The fourth and fifth columns are empty when $h \not \equiv 5
  \pmod{6}$ (we refer to this as a ``notch row''), and full otherwise.
\item The sixth column is full.
\end{itemize}

The final three columns form a ``lock'':
\begin{itemize}
\item The first column is full, except for the highest two rows.
\item The second column is full, except for the highest row.
\item The third column is empty, except for the second-highest row.
\end{itemize}


We use the piece sequence to encode the values of the elements of the
sequence $\{a_i\}$. We begin with, in order, the following sequence of
pieces for each integer $a_i$:

\begin{itemize}
\item an \emph{initiator} sequence --- $\left\langle \mathsf{I, LG,
      Sq} \right\rangle$
\item a \emph{filler} sequence, repeated $a_i$ times --- $\langle
  \mathsf{LG, LS, LG, LG, Sq} \rangle$
\item a \emph{terminator} sequence --- $\langle \mathsf{Sq, Sq} \rangle$
\end{itemize}

After the pieces for each of the integers $a_1, \ldots, a_{3s}$, a
final sequence follows:

\begin{itemize}
\item $s$ $\mathsf{I}$ pieces, to match the terminator sequences of
  the topmost groups
\item one $\mathsf{RG}$ piece, to fit into the lock
\item $\frac{3T}{2} + 5$ $\mathsf{I}$ pieces, to clear the board
\end{itemize}

This initial board state and piece sequence define a Tetris game
$\mathcal{G(P)}$ corresponding to the \textsc{3-Partition} instance
$\mathcal{P}$.


\begin{theorem}
  The Tetris game $\mathcal{G(P)}$ is polynomial in the size of its
  corresponding \textsc{3-Partition} problem $\mathcal{P}$.
\end{theorem}

\begin{proof}
  We suppose that we are given the problem $\mathcal{P} = \langle a_1,
  \ldots, a_{3s}, T \rangle$ with the integers $a_i$ and $T$ given in
  unary. This does not change the $\NP$-completeness of the problem,
  since \textsc{3-Partition} is $\NP$-complete in the strong sense.

  The size of the gameboard is $6s + 3$ columns by $6T + 22 + 3s +
  O(1)$ rows, which is polynomial in $s$ and $T$. The total number of
  pieces is
  \[\sum_{i=1}^{3s} \left[3 + 5a_i\right] + s + 1 + \frac{3T}{2} + 5
    16s + 5sT + \frac{3T}{2} + 6\]
  (applying the fact that the set of all $a_i$'s sums to $sT$).
  This is also polynomial in $s$ and $T$. Since the problem
  $\mathcal{P}$ expresses the $a_i$ and $T$ in unary, $s$ and $T$ are
  polynomial in the length of $\mathcal{P}$. So $\mathcal{G(P)}$ is
  polynomial in the size of $\mathcal{P}$.
\end{proof}


\section{Completeness}
\label{sec:completeness}
We prove the correctness of this reduction by first showing that a
``yes'' instance of \textsc{3-Partition} maps to a Tetris game where
the maximum number of rows can be cleared.

\begin{theorem}
  Suppose $\mathcal{P}$ is a ``yes'' instance of
  \textsc{3-Partition}. Define $k = 6T + 22$. There exists a valid trajectory
  sequence $\Sigma$ that clears $k$ rows.
\end{theorem}

\begin{proof}
  Let $\mathcal{P}$ be a ``yes'' instance of
  \textsc{3-Partition}. This means that there are a set of numbers
  $\{a_1, \ldots, a_{3s}\}$ that partition into a set of disjoint sets
  $\{A_1, \ldots, A_s\}$, where each $A_j$ has three elements and has
  sum $\sum_{a_i \in A_j} a_i = T$. Let $\mathcal{G(P)}$ be the
  associated Tetris game.

  \begin{figure}[ptbh]
    \centering
    \includegraphics[scale=.5]{aiblocks}
    \caption{The placement of the sequence of blocks corresponding to
    an integer $a_i$. (Demaine et al., p. 10)}
    \label{fig:aiblocks}
  \end{figure}

  \begin{figure}[pbth]
    \centering
    \includegraphics[scale=.5]{endgame}
    \caption{The reduction endgame sequence (Demaine et al., p. 10)}
    \label{fig:endgame}
  \end{figure}
  
  We generate a trajectory sequence $\Sigma$ corresponding to the
  3-partitioning $A_1, \ldots, A_s$. For each piece $a_i$, we place
  all the pieces representing it into the bucket $j$ corresponding to
  the set $A_j$ that contains $a_i$. The initiator block fits into the
  vertical indentation created by the two \textsf{Sq} blocks. The
  filler sequences fill the horizontal notches and create height;
  since the filler sequence is repeated a number of times proportional
  to the value of $a_i$, the height reflects the magnitude of $a_i$.
  The terminator blocks create another indentation to accept the next
  initiator sequence. This process is depicted in
  Figure~\ref{fig:aiblocks}. We next place $s$ \textsf{I} blocks in
  the indentations created by the final terminator blocks, as in
  Figure~\ref{fig:endgame}(b).
  
  The result is that we are able to fill the buckets completely: each
  bucket contains three initiator and terminator sequences, which
  together take up 22 rows, including the four rows at the bottom that
  were partially filled and the final $s$ \textsf{I} blocks, and each
  filler sequence fills six rows. Since each integer $a_i$ contains
  $a_i$ filler sequences, and all the $a_i$'s in a set $A_j$ sum to
  $T$ because the $A_j$'s form a 3-partitioning, the filler sequences
  together fill $6T$ rows. Combined with the other 22, this is $6T+22
  = k$ rows, the height of the gameboard.
  
  The next piece is a \textsf{RG} piece. This piece fits into the
  lock, as shown in Figure~\ref{fig:endgame}(c) causing the top two
  rows to be completely filled. They are then cleared from the
  gameboard, making it possible to place blocks into the
  previously-blocked rightmost column. The remaining pieces are
  \textsf{I} blocks, and there are just enough of them to clear the
  entire remaining board by placing them into this column.

  Thus, we can clear $k = 6T+22$ rows if there is a valid
  3-partitioning of the \textsc{3-Partition} instance $\mathcal{P}$.
\end{proof}


\section{Soundness}
\label{sec:soundness}

We now show that, given a Tetris game $\mathcal{G(P)}$ mapped from a
\textsc{3-Partition} instance $\mathcal{P}$, $k = 6T+22$ rows can be
cleared in $\mathcal{G(P)}$ only if $\mathcal{P}$ has a valid
3-partitioning.

In general, this sort of result seems difficult to prove, since there
are so many ways that a Tetris game might proceed. Fortunately,
however, for the games we consider, gameplay is actually quite
restricted. Since we are checking only for an optimal solution, many
legal moves that would lead to a non-optimal solution (clearing less
than $k$ rows) can be ignored. We refer to such moves as
\emph{invalid}.

\begin{lemma}
No piece can ever be placed such that any part of it extends above row
$6T+22$.  
\end{lemma}

\begin{proof}
  The proof is by counting. We first count the number of empty squares
  in the gameboard. In each of the $s$ buckets, the first two columns
  are empty except for the first four rows, the third is entirely
  empty, the fourth and fifth contain $T+3$ empty rows, and the sixth
  is entirely full. There are two and one empty spaces in the first
  two columns of the lock respectively, and $6T + 21$ in the
  third. Thus, there are a total of $64s+20sT+6T+24$ empty squares in
  the $6T+22$ rows of the initial board.

  We then count the number of squares used by the pieces. There are
  four squares per piece. From above, we have $16s + 5sT +
  \frac{3T}{2} + 6$, so $64s + 20sT + 6T+24$ squares. This is
  precisely the same number as the number of empty squares.

  The total number of partially filled rows used by the initial
  gameboard is $6T+22$, and there are just enough squares in the piece
  sequence to complete these rows. Thus, the only way to clear $6T+22$
  rows is to use every empty square in the initial gameboard. If any
  piece is placed somewhere else, there will not be enough pieces to
  clear $6T+22$ rows. Thus, any valid solution will not have any
  pieces above row $6T+22$.
\end{proof}


\begin{lemma}
  No piece can be placed in the lock before the \textsf{RG} piece.
\end{lemma}

\begin{proof}
  The proof is immediate by tiling --- any other piece available
  (\textsf{I, LG, LS,} or \textsf{Sq}) cannot fit into the columns of
  the lock without extending above the $6T+22$nd row.
\end{proof}

\begin{corollary}
  No rows can be cleared before the \textsf{RG} piece is placed in the
  lock.
\end{corollary}

\begin{proof}
  The right column of the lock will always be empty until the top two
  rows are cleared, and this cannot be accomplished without the \textsf{RG}.
\end{proof}

Therefore, all the pieces before the \textsf{RG} must be placed in the
buckets, completely filling them, without clearing any rows. This is
even more restrictive, since there are certain situations that, if
they should arise, mean a bucket cannot be completely filled:

\begin{lemma}
  Any trajectory that leads to a unfillable bucket configuration is
  invalid.
\end{lemma}

\begin{proof}
  If a bucket cannot be filled, there is no way to fill all of the
  buckets, and thus a piece must be placed above the $6T+22$nd row
  before the \textsf{RG}. Since no rows can be cleared before the
  \textsf{RG}, there is no way for an unfillable bucket to become
  fillable again.
\end{proof}


Examples of unfillable buckets are shown in
Figure~\ref{fig:unfillable}. Perhaps the most straightforward is the
\emph{hole}: an empty space surrounded by filled squares, as in
Figure~\ref{fig:unfillable}(a). The hole clearly cannot be filled
without removing some row, which is not possible. The arguments that
the rest are unfillable are rather tedious arguments by tiling of
pieces; the interested reader is referred to Demaine's paper for the
details.

\begin{figure}[htbp]
  \centering
  \includegraphics[scale=.5]{unfillable}
  \caption{Examples of unfillable buckets (Demaine et al., p. 14)}
  \label{fig:unfillable}
\end{figure}

These unfillable configurations and similar arguments by tiling lead
us to the conclusion that the only valid, fillable configurations for
a bucket are the ones in Figure~\ref{fig:fillable}. Note that
initially all buckets are in the ``unprepped'' configuration. We use
this to show the soundness of the strategy used in the completeness
proof of our reduction.

\begin{figure}[hbtp]
  \centering
  \includegraphics[scale=.5]{fillable}
  \caption{The only valid fillable bucket configurations (Demaine et al., p. 16)}
  \label{fig:fillable}
\end{figure}

\begin{lemma}
  \label{lem:init}
  Starting with a unprepped configuration, the only valid placement of
  an initiator sequence leads to an overflat bucket.
\end{lemma}

\begin{lemma}
  \label{lem:fill}
  For the filler sequence, there are two possibilities:
  \begin{enumerate}
  \item If the initial configuration has an overflat bucket, then
  either
    \begin{enumerate}
    \item all the pieces can be placed into the overflat bucket,
      leading to the same bucket being overflat again, or
    \item the first two pieces can be placed into the overflat bucket,
      giving a tall-plateau bucket, and the remaining can be placed in
      another bucket, giving a trigger-happy bucket.
    \end{enumerate}
  \item If the initial configuration has a tall-plateau bucket and a
    trigger-happy bucket, no valid placement exists.
  \end{enumerate}
\end{lemma}

\begin{lemma}
  \label{lem:term}
  For the terminator sequence, there are again two possibilities:
  \begin{enumerate}
  \item If the initial configuration has an overflat bucket, then
    all the pieces can be placed in this bucket, returning the bucket
    to an unprepped configuration.
  \item If the initial configuration has a tall-plateau bucket and a
    trigger-happy bucket, no valid placement exists.
  \end{enumerate}
\end{lemma}

\begin{proof}
  The proof of these three lemmas is by tiling, and is omitted.
\end{proof}

\begin{lemma}
  For the sequence of blocks corresponding to an integer $a_i$, all of
  these blocks must be placed in the same bucket.
\end{lemma}

\begin{proof}
  Immediate from
  Lemmas~\ref{lem:init},~\ref{lem:fill},~\ref{lem:term}.
\end{proof}

\begin{lemma}
  If all blocks corresponding to the integers $a_i$ have been placed
  in an unprepped configuration such that there are $4s$ empty
  gridsquares in the buckets, then the only valid strategy exists if
  there are 4 empty squares in a vertical indentation in each bucket,
  and the strategy is to place the following $s$ \textsf{I} blocks in
  this indentation.
\end{lemma}

\begin{proof}
  Since the configuration is unprepped with $4s$ empty squares, either
  they must all have their highest portion at the $6T+22$nd row, or
  one extends above this row. In the latter case, the configuration is
  invalid. In the former case, the $s$ \textsf{I} blocks can be placed
  in the indentations.
\end{proof}

Armed with these lemmas, we can now prove the soundness of the
reduction.

\begin{theorem}
  If $\mathcal{G(P)}$ has a valid strategy, then $\mathcal{P}$ has a
  3-partitioning.
\end{theorem}

\begin{proof}
  Suppose $\mathcal{G(P)}$ is a Tetris game with a valid strategy. We
  concern ourselves with the pieces placed before the \textsf{RG}
  piece. By the lemma above, all these pieces must have been placed in
  the buckets, and all the pieces corresponding to each integer $a_i$
  must have been placed into the same bucket. Including the series of
  $s$ \textsf{I} blocks immediately before the \textsf{RG} block,
  we count that there are $20T+64$ squares that must have been
  filled.

  Let $A_j$ be the set of $a_i$ that are represented by the blocks
  placed in the $j$th bucket. By our previous counting, we know that
  the $j$th bucket must contain $\sum_{a_i \in A_j} \left(3 + 5a_i +
  2\right)$ blocks corresponding to the $a_i$, plus four corresponding
  to the \textsf{I}. Since each block takes up four squares, and the
  number of squares must equal the number of unfilled squares in the
  initial configuration, we have
  \[20T + 64 = 4 + \sum_{a_i\in A_j} 4\left(3 + 5a_i +
    2\right)\]
  or
  \[20T + 60 = \sum_{a_i\in A_j} \left(20 a_i + 20\right)\]

  Since we arranged for the $a_i$ and $T$ to satisfy the technical
  conditions that
  \begin{itemize}
  \item For any set $S \subset \left\{a_1,\ldots,a_{3s}\right\}$ with
    $\sum_{a_i\in S} a_i = T$, $\abs{S} = 3$
  \item If $\sum_{a_i \in A_j} a_i \neq T$, then $\abs{T- \sum_{a_i \in
        A_j} a_i} \ge 3s$
  \end{itemize}

  it follows that $\sum_{a_i \in A_j} = T$ and $\abs{A_j} =
  3$. Therefore, the sets $A_j$ form a 3-partitioning of
  $\mathcal{P}$.
 
\end{proof}

\section{The punchline}
\label{sec:punchline}

\begin{theorem}
  \textsc{3-Partition} is reducible to \textsc{Tetris-$k$-cleared-rows}
\end{theorem}

\begin{proof}
  We have proven that our reduction from \textsc{3-Partition} to
  \textsc{Tetris-$k$-cleared-rows} results in a Tetris game in which
  $k = 6T+22$ rows can be cleared if and only if a 3-partitioning for
  the corresponding \textsc{3-Partition} instance exists. Thus,
  \textsc{3-Partition} is reducible to
  \textsc{Tetris-$k$-cleared-rows}.
\end{proof}

\begin{corollary}
  \textsc{Tetris-$k$-cleared-rows} is $\NP$-complete.
\end{corollary}

\begin{proof}
  We have shown \textsc{Tetris-$k$-cleared-rows} is in $\NP$, and the
  $\NP$-complete problem \textsc{3-Partition} reduces to it. Thus, it
  is $\NP$-complete itself.
\end{proof}

\end{document}